Problem 1719 Spy NetworkAccept: 41 Submit: 169
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
take bribes, and if we give a number of dollars to them, they are willing to hand over all their evidences they have. Therefore, if we are able to buy some spies, we would control the whole spy network.
control all spies, output minimal dollars required, otherwise output each spies we cannot control.
Input
The input consists of several test cases.For each case,the first line of input is an integer n. The second line is an integer p (1<=p<=n), which is the number of spies who accept dollars.Then
following p lines, each of them contains two integers indicating the label of spies and the number he needs. An integer r (1 <= r <= 8000) followed, then r lines. Each contains two integers A and B, which means that Spy A has the evidence of Spy B.
following p lines, each of them contains two integers indicating the label of spies and the number he needs. An integer r (1 <= r <= 8000) followed, then r lines. Each contains two integers A and B, which means that Spy A has the evidence of Spy B.
Output
For each case, If we can control all spies, output “YES” in the first line and the minimal number of dollar we need in the second line. If we cannot, output “NO” in the first line and the label
of spy that we cannot control and have the minimal number of label.
of spy that we cannot control and have the minimal number of label.
Sample Input
321 102 10021 32 3421 1004 20021 23 4
Sample Output
YES110NO3
Source
FZU 2009 Summer Training Qualification -- Hero Revival 1
分析：缩点后的价值取环内最小的价值,然后把入度为0的间谍全部买下来是去省钱的方式,如果不能买就输出NO
代码：
#include<cstdio>
#define min(a,b) a<b?a:b
using namespace std;
const int mm=8008;
const int mn=3003;
const int oo=1000000000;
int s[mm],t[mm],p[mm];
int h[mn],id[mn],q[mn],dfn[mn],low[mn],w[mn],x[mn];
int i,j,k,n,m,tsp,qe,cnt,ans;
void dfs(int u)
{
int i,v;
dfn[u]=low[u]=++tsp;
q[qe++]=u;
for(i=h[u];i>=0;i=p[i])
if(!dfn[v=t[i]])
dfs(v),low[u]=min(low[u],low[v]);
else if(id[v]<0)low[u]=min(low[u],dfn[v]);
if(low[u]==dfn[u])
{
id[u]=++cnt;
while((v=q[--qe])!=u)id[v]=cnt;
}
}
void tarjan()
{
int i;
for(qe=tsp=cnt=i=0;i<=n;++i)dfn[i]=0,id[i]=-1;
for(i=1;i<=n;++i)
if(!dfn[i])dfs(i);
}
int main()
{
while(scanf("%d%d",&n,&m)!=-1)
{
for(i=1;i<=n;++i)w[i]=oo,h[i]=-1;
while(m--)scanf("%d%d",&i,&j),w[i]=j;
scanf("%d",&m);
for(k=0;k<m;++k)
{
scanf("%d%d",&i,&j);
s[k]=i,t[k]=j,p[k]=h[i],h[i]=k;
}
tarjan();
for(i=1;i<=cnt;++i)x[i]=oo,q[i]=0;
for(i=1;i<=n;++i)x[id[i]]=min(x[id[i]],w[i]);
for(k=0;k<m;++k)
if(id[s[k]]!=(i=id[t[k]]))++q[i];
for(i=1;i<=cnt;++i)
if(!q[i]&&x[i]>=oo)break;
if(i<=cnt)
{
printf("NO\n");
for(j=1;j<=n;++j)
if(id[j]==i)break;
printf("%d\n",j);
continue;
}
for(ans=0,i=1;i<=cnt;++i)
if(!q[i]&&x[i]<oo)ans+=x[i];
printf("YES\n%d\n",ans);
}
return 0;
}