题目描述
有n个间谍，每个间谍手里有其他间谍的资料，有p个间谍愿意被收买，问能否获得所有间谍的资料，能，就输出最小花费，否则输出不能被控制的间谍中编号最小的一个。
思路
如果间谍手中的资料形成一个环，我们就只需要收买这个环上原因被收买的最小金额的人。因此我们可以缩点，缩点后的点权即为强连通分量中愿意被收买的间谍的最小金额。所以对于缩点后的DAG，我们只需要考虑入度为0的点，因为若入度为0的点必须收买，否则就无法获得它的资料，而收买其他点必定会使总花费增加。而如果不能得到所有资料，那么不能控制的间谍有两种可能：①入度为0且不能被收买；②入度为1且由第一种可能中的人转移过来。我们只需要统计这当中编号最小的即可。
#include <bits/stdc++.h> using namespace std; const int N=3300,M=8800; struct Edge { int x,y; }e[M]; int nxt[M],head[N],to[M],tot; void add_edge(int x,int y) { nxt[++tot]=head[x]; head[x]=tot; to[tot]=y; e[tot].x=x;e[tot].y=y; } int read() { int res=0,w=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)w=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){res=(res<<3)+(res<<1)+ch-‘0‘;ch=getchar();} return res*w; } int dfn[N],low[N],st[N],co[N],cc[N],top,idx,col,v[N]; void tarjan(int u) { dfn[u]=low[u]=++idx; st[++top]=u; for(int i=head[u];i;i=nxt[i]) { int v=to[i]; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(!co[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { co[u]=++col; while(st[top]!=u) { co[st[top]]=col; --top; } --top; } } int in[N]; int main() { int n,p,r; n=read();p=read(); for(int i=1;i<=p;i++) { int x=read(); v[x]=read(); } r=read(); for(int i=1;i<=r;i++) { int a=read(),b=read(); add_edge(a,b); } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); for(int i=1;i<=r;i++) { int u=co[e[i].x],v=co[e[i].y]; if(u!=v) in[v]++; } int ans=0,cnt=0; for(int i=1;i<=n;i++) if(!in[co[i]]) { if(v[i]==0) { cnt=cnt==0?i:min(cnt,i); //情况1 for(int j=head[i];j;j=nxt[j]) if(j<cnt&&!v[i]&&in[co[j]]==1)//情况2 cnt=j; } else ans+=v[i]; } if(cnt==0)printf("YES\n%d",ans); else printf("NO\n%d",cnt); }
原文：https://www.cnblogs.com/fangbozhen/p/11728561.html