间谍网络

描述 Description

由于外国间谍的大量渗入，国家安全正处于高度危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍接受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。
我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有n个间谍（n不超过3000），每个间谍分别用1到3000的整数来标识。
请根据这份资料，判断我们是否可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。

输入格式 InputFormat

一行只有一个整数n。
第二行是整数p。表示愿意被收买的人数，1<=p<=n。
接下来的p行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过20000.
紧跟着一行只有一个整数r，1<=r<=8000。然后r行，每行两个正整数，表示数对（A，B），A间谍掌握B间谍的证据。

输出格式 OutputFormat

如果可以控制所有间谍，第一行输出YES，并在第二行输出所需要支付的贿金最小值。否则输出NO，并在第二行输出不能控制的间谍中，编号最小的间谍编号。

做的第一道图论题，tarjan算法。

  1 #include<iostream>
  2 #include<fstream>
  3 #define fin cin
  4 using namespace std;
  5 
  6 int n,p,r;
  7 
  8 int money[4000];bool map[4000][4000];
  9 void Init(){
 10      fin>>n>>p;
 11      for(int i=1;i<=n;++i)
 12      money[i]=100000000;
 13      
 14      for(int i=1;i<=p;++i)
 15      {int num;fin>>num;fin>>money[num];}
 16      
 17      fin>>r;
 18      for(int i=1;i<=r;++i)
 19      {int a,b;fin>>a>>b;map[a][b]=1;}
 20      }
 21 
 22 int times=0,mintime[4000];
 23 int stack[4000],top=0;
 24 int sum=0,f[4000];int lin[4000][4000];
 25 bool mark[4000],vis[4000];
 26 
 27 void Dfs(int k){
 28      times++;
 29      int now;
 30      vis[k]=1;top++;stack[top]=k;
 31      now=mintime[k]=times;
 32      
 33      for(int i=1;i<=n;++i)
 34      if(map[k][i])
 35      {
 36        if(mark[i]) continue;
 37        if(!vis[i]) Dfs(i);
 38        if(mintime[k]>mintime[i])
 39        mintime[k]=mintime[i];
 40              }
 41      
 42      if(mintime[k]==now)
 43      {
 44        sum++;
 45        while(stack[top]!=k)
 46        {
 47          lin[sum][0]++;
 48          lin[sum][lin[sum][0]]=stack[top];
 49          mark[stack[top]]=1;
 50          f[stack[top]]=sum;
 51          top--;
 52                            }
 53        lin[sum][0]++;
 54        lin[sum][lin[sum][0]]=stack[top];
 55        mark[stack[top]]=1;
 56        f[stack[top]]=sum;
 57        top--;                 
 58                         }
 59      }
 60 
 61 bool q=1;int indegree[4000]={0};
 62 int ans=0,cord[4000],t=0;
 63 void Count(){
 64      for(int i=1;i<=sum;++i)
 65      if(indegree[i]==0)
 66      {
 67        int mi=100000000;
 68        for(int j=1;j<=lin[i][0];++j)
 69        if(money[lin[i][j]]<mi) mi=money[lin[i][j]];
 70        
 71        if(mi==100000000) {q=0;cord[++t]=i;}
 72        else ans+=mi;
 73                      }
 74      }
 75 
 76 void Print(){
 77      if(q==0)
 78      {
 79        cout<<"NO"<<endl;
 80        ans=100000;
 81        
 82        for(int i=1;i<=t;++i)
 83        for(int j=1;j<=lin[cord[i]][0];++j)
 84        if(lin[cord[i]][j]<ans) ans=lin[cord[i]][j];
 85        cout<<ans<<endl;
 86        return ; 
 87             }
 88     
 89      cout<<"YES"<<endl<<ans<<endl;
 90      return ;
 91      }
 92      
 93 
 94 int main()
 95 {
 96     Init();
 97     
 98     for(int i=1;i<=n;++i)
 99     if(!mark[i]) Dfs(i);
100     
101     for(int i=1;i<=n;++i)
102     for(int j=1;j<=n;++j)
103     if(map[i][j]&&f[i]!=f[j]) indegree[f[j]]++;
104     
105     Count();
106     Print();
107     return 0; 
108     }