洛谷 P1262 间谍网络

传送门

题目大意：A能揭发B，B能揭发C..某些人可以被收买，如果收买A，那么A,B,C..的情报都可以得到。

求能否得到所有情报，如果可以最少花费多少钱去收买。

题解：tajian缩点

dfs/bfs从能收买的人遍历图，如果全部都能遍历，那么可以得

到所有的情报。然后tarjan缩点，并记录缩的每一个点的收买的

最小值，不能收买的人设收买他的花费是正无穷。统计入度为0

的点的收买花费和。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 3020

#define inf 0x3f3f3f3f

using namespace std;

int n,p,r,sumedge,top,tim,sumclr,cnt,ans,tot;

int head[maxn],Stack[maxn],instack[maxn],low[maxn];

int vis[maxn],dfn[maxn],cw[maxn],rd[maxn],w[maxn],bel[maxn];

struct Edge{

    int x,y,nxt;

    Edge(int x=,int y=,int nxt=):

        x(x),y(y),nxt(nxt){}

}edge[maxn*];

void add(int x,int y){

    edge[++sumedge]=Edge(x,y,head[x]);

    head[x]=sumedge;

}

void dfs(int x){

    if(vis[x])return;

    vis[x]=true;++tot;

    for(int i=head[x];i;i=edge[i].nxt){

        int v=edge[i].y;

        dfs(v);

    }

}

void Tarjian(int x){

    low[x]=dfn[x]=++tim;

    Stack[++top]=x;instack[x]=true;

    for(int i=head[x];i;i=edge[i].nxt){

        int v=edge[i].y;

        if(instack[v])low[x]=min(low[x],dfn[v]);

        else if(!dfn[v]){

            Tarjian(v);low[x]=min(low[x],low[v]);

        }

    }

    if(low[x]==dfn[x]){

        sumclr++;cw[sumclr]=inf;

        while(Stack[top+]!=x){

            bel[Stack[top]]=sumclr;

            cw[sumclr]=min(cw[sumclr],w[Stack[top]]);

            instack[Stack[top--]]=false;

        }

    }

}

int main(){

    scanf("%d%d",&n,&p);

    memset(w,0x3f,sizeof(w));

    for(int i=;i<=p;i++){

        int x,y;

        scanf("%d%d",&x,&y);w[x]=y;

    }

    scanf("%d",&r);

    for(int i=;i<=r;i++){

        int a,b;

        scanf("%d%d",&a,&b);

        add(a,b);

    }

    for(int i=;i<=n;i++)if(w[i]!=inf)dfs(i);

    if(tot!=n){

        for(int i=;i<=n;i++)

         if(vis[i]==){

             printf("NO\n");

             printf("%d\n",i);

             return ;

         }

    }

    for(int i=;i<=n;i++)if(!dfn[i])Tarjian(i);

    for(int x=;x<=n;x++){

        for(int i=head[x];i;i=edge[i].nxt){

            int v=edge[i].y;

            if(bel[x]!=bel[v])rd[bel[v]]++;

        }

    }

    for(int i=;i<=sumclr;i++)

     if(rd[i]==)ans+=cw[i];

    printf("YES\n%d\n",ans);

    return ;

}