Description
由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果 \(A\) 间谍手中掌握着关于 \(B\) 间谍的犯罪证据，则称 \(A\) 可以揭发 \(B\)。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。 我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有 \(n\) 个间谍( \(n\) 不超过3000)，每个间谍分别用1到3000的整数来标识。 请根据这份资料，判断我们是否有可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。
第一行只有一个整数 \(n\) 。
第二行是整数 \(p\) 。表示愿意被收买的人数，\(1 \leq p \leq n\) 。
接下来的 \(p\) 行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过20000。
紧跟着一行只有一个整数 \(r\)，\(1 \leq r \leq 8000\) 。然后 \(r\) 行，每行两个正整数，表示数对 \((A, B)\)，\(A\) 间谍掌握 \(B\) 间谍的证据。
Output
如果可以控制所有间谍，第一行输出 \(YES\)，并在第二行输出所需要支付的贿金最小值。否则输出 \(NO\)，并在第二行输出不能控制的间谍中，编号最小的间谍编号。
3 2 1 10 2 100 2 1 3 2 3
Sample Output
YES 110
题解
前半部分不难想，\(tarjan\) 缩点，记录每个强连通分量中的编号最小值及要支付的最小现金（如果有可被收买的间谍的话） 接下来我一开始有点懵，后来看了题解才明白，只需把缩点后那些入度为0的点要支付的最小现金加起来就行了，如果存在一个入度为0的点中没有可被收买的间谍的话则原题无解。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define INF 40000
using namespace std;
const int N = 3005;
typedef pair<int,int> P;
struct node{
int v;
node *next;
}pool[N*3],*h[N];
int cnt,cnt2;
void addedge(int u,int v){
node *p=&pool[++cnt];
p->v=v;p->next=h[u];h[u]=p;
}
int n,m;
int val[N],dfn[N],low[N],tot,vis[N];
int st[N],top,scc[N],sccno,mn[N],minv[N];
void dfs(int u){
int v;
dfn[u]=low[u]=++tot;
st[top++]=u; vis[u]=1;
for(node *p=h[u];p;p=p->next)
if(!vis[v=p->v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]==1) low[u]=min(low[u],dfn[v]);
if(low[u]==dfn[u]){
sccno++;
minv[sccno]=INF; mn[sccno]=n+1;
for(;;){
v=st[--top];
scc[v]=sccno;
minv[sccno]=min(minv[sccno],val[v]);
mn[sccno]=min(mn[sccno],v);
vis[v]=2;
if(u==v) break;
}
}
}
int in[N];
P ed[N*3];
int main()
{
int x;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) val[i]=INF;
for(int i=0;i<m;i++)
scanf("%d",&x),scanf("%d",&val[x]);
scanf("%d",&m);
for(int i=0;i<m;i++)
scanf("%d%d",&ed[i].first,&ed[i].second),addedge(ed[i].first,ed[i].second);
for(int i=1;i<=n;i++)
if(!dfn[i]) dfs(i);
for(int i=0;i<m;i++)
if(scc[ed[i].first]!=scc[ed[i].second])
in[scc[ed[i].second]]++;
int Mnum=n+1,Mval=0;
for(int i=1;i<=sccno;i++)
if(in[i]==0){
if(minv[i]==INF) Mnum=min(Mnum,mn[i]);
else Mval+=minv[i];
}
if(Mnum==n+1) printf("YES\n%d\n",Mval);
else printf("NO\n%d\n",Mnum);
return 0;
}
转载于:https://www.cnblogs.com/lindalee/p/9852437.html
相关资源：数据结构—成绩单生成器
