关键字：强连通分量，缩点。
Link&Limit
时间限制：1000ms 空间限制：131072kb
Description
由于外国间[防和谐]谍的大量渗入，国[防和谐]家安全正处于高度的危机之中。如果A间[防和谐]谍手中掌握着关于B间[防和谐]谍的犯[防和谐]罪证据，则称A可以揭发B。有些间[防和谐]谍收受贿[防和谐]赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间[防和谐]谍的话，我们就可能控制间[防和谐]谍网中的每一分子。因为一旦我们逮捕了一个间[防和谐]谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间[防和谐]谍，掌握新的情报。
我们的反间[防和谐]谍机关提供了一份资料，色括所有已知的受[防和谐]贿的间[防和谐]谍，以及他们愿意收受的具体数额。同时我们还知道哪些间[防和谐]谍手中具体掌握了哪些间[防和谐]谍的资料。假设总共有n个间[防和谐]谍(n不超过3000)，每个间[防和谐]谍分别用1到3000的整数来标识。
请根据这份资料，判断我们是否有可能控制全部的间[防和谐]谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间[防和谐]谍。
Input Format
第一行只有一个整数n。
第二行是整数p。表示愿意被收买的人数，1≤p≤n。
接下来的p行，每行有两个整数，第一个数是一个愿意被收买的间[防和谐]谍的编号，第二个数表示他将会被收买的数额。这个数额不超过20000。
紧跟着一行只有一个整数r，1≤r≤8000。然后r行，每行两个正整数，表示数对(A, B)，A间[防和谐]谍掌握B间[防和谐]谍的证据。
Output Format
如果可以控制所有间[防和谐]谍，第一行输出YES，并在第二行输出所需要支付的贿[防和谐]金最小值。否则输出NO，并在第二行输出不能控制的间[防和谐]谍中，编号最小的间[防和谐]谍编号。
Sample Input #1
3
2
1 10
2 100
2
1 3
2 3
Sample Output #1
YES
110
Sample Input #2
4
2
1 100
4 200
2
1 2
3 4
Sample Output #2
NO
3
由题可以构造出一张有向图，可知在同一强连通分量中，只要有一个点被收买，剩下的点就会被揭发。这样，我们只需要将所有强连通分量找出来，并将每个强连通 分量缩成一个点，再考虑缩点后入度为零的点能否收买就可以了。记录每一个强连通分量中最便宜的点，以及编号最小的点。如果可以收买，则答案为每个入度为零 的点中最便宜的点价格之和；如果不能收买，输出编号最小的点即可。
关于如何求强连通分量，这里写得不错：https://www.byvoid.com/blog/scc-tarjan/
#include <stdio.h>
int n,m,val[3010],ans = 0;
int e[8010][2],p[3010],bel[3010],deg[3010],minv[3010],minid[3010],bCnt = 0;
int dfn[3010],low[3010],tot = 0,stack[3010],top = 0;
short inS[3010];
int min(int a,int b)
{
return a<b?a:b;
}
void adde(int sn,int fn,int id)
{
e[id][0] = fn; e[id][1] = p[sn]; p[sn] = id;
}
void tarjan(int sn)
{
int i,fn;
dfn[sn] = low[sn] = ++tot;
stack[++top] = sn; inS[sn] = 1;
for(i=p[sn];i;i=e[i][1])
{
fn = e[i][0];
if(!low[fn])
{
tarjan(fn);
low[sn] = min(low[sn],low[fn]);
}
else if(inS[fn]) low[sn] = min(low[sn],low[fn]);
deg[bel[fn]]++;
}
if(dfn[sn] == low[sn])
{
bCnt++;
do
{
fn = stack[top--];
inS[fn] = 0;
bel[fn] = bCnt;
minv[bCnt] = min(minv[bCnt],val[fn]);
minid[bCnt] = min(minid[bCnt],fn);
}
while(fn != sn);
}
}
int main()
{
int i,x,y;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) val[i] = minv[i] = minid[i] = 999999999;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
val[x] = y;
}
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
adde(x,y,i);
}
for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
for(i=1;i<=bCnt;i++) if(!deg[i])
{
if(minv[i]<99999) ans += minv[i];
else { ans = minid[i]; break;}
}
if(i<=bCnt) printf("NO\n%d",ans);
else printf("YES\n%d",ans);
return 0;
}
评论 (0)
