loj10095 间谍网络

题目描述
由于外国间谍的大量渗入，国家安全正处于高度危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍接受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。

我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有n个间谍，每个间谍分别用1到n的整数来标识。

请根据这份资料，判断我们是否可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。
输入格式
第一行只有一个整数n。第二行是整数p。表示愿意被收买的人数。

接下来的p行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。

紧跟着一行只有一个整数r。然后r行，每行两个正整数，表示数对(A,B) ，A间谍掌握B间谍的证据。
输出格式
如果可以控制所有间谍，第一行输出YES，并在第二行输出所需要支付的贿金最小值。否则输出NO，并在第二行输出不能控制的间谍中，编号最小的间谍编号。
样例
样例输入

2
1
2 512
2
1 2
2 1

样例输出

YES
512

数据范围与提示
1<=n<=3000,1<=p<=n,1<=r<=8000，每个收买的费用为非负数且不超过20000。

------------------------------------------------------------------------------------------------------------------

首先，将各个强连通分量进行缩点，建立新图，求出第一分量的入度。

然后，并记录每一个分量中的最小点编号和分量内点中能买通的最少花费。

第三，把每一个分量标明是否可以被买通，入度为0的分量的最小花费和就是整个图的最少花费和。

第四步，拓扑排序，把所有可以买通的点的后续点都设为可以买通。

第五步，所有不可买通的分量中编号最小的点的编号就是不可买通的最小编号。

最后，通过最小编号是否求出可以判断是否可以全部买通。从而输出相应的内容。

------------------------------------------------------------------------------------------------------------------

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 const int maxn=3010;

  4 const int maxm=8010;

  5 int n,m,p;

  6 struct edge

  7 {

  8     int u,v,nxt;

  9 }e[maxm];

 10 int head[maxn],js;

 11 void addage(int u,int v)

 12 {

 13     e[++js].u=u;e[js].v=v;

 14     e[js].nxt=head[u];head[u]=js;

 15 }

 16 int sm[maxn][2];

 17 int dfn[maxn],low[maxn],st[maxn],top,cnt,lt[maxn],lts;

 18 void tarjan(int u)

 19 {

 20     dfn[u]=low[u]=++cnt;

 21     st[++top]=u;

 22     for(int i=head[u];i;i=e[i].nxt)

 23     {

 24         int v=e[i].v;

 25         if(!dfn[v])

 26         {

 27             tarjan(v);

 28             low[u]=min(low[u],low[v]);

 29         }

 30         else if(!lt[v])

 31             low[u]=min(low[u],dfn[v]);

 32     }

 33     if(low[u]==dfn[u])

 34     {

 35         lt[u]=++lts;

 36         while(st[top]!=u)lt[st[top--]]=lts;

 37         --top;

 38     }

 39 }

 40 int rd[maxn],msm[maxn];

 41 edge ee[maxm];

 42 int headd[maxn],jss;

 43 void addagee(int u,int v)

 44 {

 45     ee[++jss].u=u;ee[jss].v=v;

 46     ee[jss].nxt=headd[u];headd[u]=jss;

 47 }

 48 queue<int>q;

 49 bool ksm[maxn];

 50 int mno[maxn];

 51 int ans,mbk=0x7f7f7f7f;

 52 int main()

 53 {

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

 55     for(int i=1;i<=p;++i)

 56         scanf("%d%d",&sm[i][0],&sm[i][1]);

 57     scanf("%d",&m);

 58     for(int u,v,i=0;i<m;++i)

 59     {

 60         scanf("%d%d",&u,&v);

 61         addage(u,v);

 62     }

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

 64         if(!dfn[i])tarjan(i);

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

 66         for(int j=head[i];j;j=e[j].nxt)

 67         {

 68             if(lt[i]!=lt[e[j].v])

 69             {

 70                 rd[lt[e[j].v]]++;

 71                 addagee(lt[i],lt[e[j].v]);

 72             }

 73         }

 74     memset(msm,0x7f,sizeof msm);

 75     memset(mno,0x7f,sizeof mno);

 76     for(int i=1;i<=p;++i)

 77         if(msm[lt[sm[i][0]]]>sm[i][1])msm[lt[sm[i][0]]]=sm[i][1],ksm[lt[sm[i][0]]]=1;

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

 79         if(i<mno[lt[i]])mno[lt[i]]=i;

 80     for(int i=1;i<=lts;++i)

 81         if(rd[i]==0)q.push(i),ans+=msm[i];

 82     while(!q.empty())

 83     {

 84         int u=q.front();q.pop();

 85         for(int i=headd[u];i;i=ee[i].nxt)

 86         {

 87             int v=ee[i].v;

 88             rd[v]--;

 89             if(ksm[u])ksm[v]=1;

 90             if(rd[v]==0)q.push(v);

 91         }

 92     }

 93     for(int i=1;i<=lts;++i)

 94     {

 95         if(!ksm[i])mbk=min(mbk,mno[i]);

 96     }

 97     if(mbk==0x7f7f7f7f)printf("YES\n%d",ans);

 98     else printf("NO\n%d",mbk);

 99     return 0;

100 }

巴特西

loj10095 间谍网络

最新文章

热门文章