题目描述
由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。
我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有n个间谍(n不超过3000)，每个间谍分别用1到3000的整数来标识。
请根据这份资料，判断我们是否有可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。
输入输出格式
输入格式：
第一行只有一个整数n。
第二行是整数p。表示愿意被收买的人数，1≤p≤n。
接下来的p行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过20000。
紧跟着一行只有一个整数r，1≤r≤8000。然后r行，每行两个正整数，表示数对(A, B)，A间谍掌握B间谍的证据。
输出格式：
如果可以控制所有间谍，第一行输出YES，并在第二行输出所需要支付的贿金最小值。否则输出NO，并在第二行输出不能控制的间谍中，编号最小的间谍编号。
输入输出样例
输入样例#1：
321 102 10021 32 3
输出样例#1：
YES110
输入样例#2：
421 1004 20021 23 4
输出样例#2：
NO3
算法
缩点
思路
如果A掌握B的信息，那么我们就建有向边A->B，构成一个图。
每个点的权值就是收买该间谍需要花的钱，如果不能收买，那就赋为\(\infty\)。 我们的任务就是取Sum(点权)最少的若干个点，以这几个点为起点，能遍历整张图。 当然，Sum(点权)不能为\(\infty\)。（注意下 \(\infty + \infty = \infty \ \ ,\infty + x = \infty\)）因为在一个强连通分量中，任何一个点都能遍历到每个节点。所以，对于一个强连通分量，完全可以看成一个点，点权为该强连通分量包含的点的最小点权。
所以缩点即可。以下所说的点均为“缩”过的点。
入度为0的点绝对要取，而取来后绝对已经所有点都能访问到。
这个很好证明。入度为0的点绝对要取是不难理解的，因为它不可能被其他点访问。由于缩点后的图不可能构成环，所以入度不为0的点肯定可以被已经访问过的点访问到。
注意下不能被控制的(编号最小)点不一定入度为0。
如这组数据:
Input Data
414 10042 42 14 31 3
Output Data
NO1
代码
#includeusing namespace std;#define MAXN 3005#define MAXM 8005int n, p, r;int hd[MAXN], nxt[MAXM], to[MAXM], tot(1);int dfn[MAXN], low[MAXN], num, stk[MAXN], tp, c[MAXN], cnt;int pr[MAXN], f[MAXN];int x, y;bool vs[MAXN], v[MAXN];void Add( int x, int y){ nxt[++tot] = hd[x]; hd[x] = tot; to[tot] = y; }void Tarjan( int x ){ dfn[x] = low[x] = ++tot; stk[++tp] = x; for ( int i = hd[x]; i; i = nxt[i] ){ if ( !dfn[to[i]] ) Tarjan( to[i] ), low[x] = min( low[x], low[to[i]] ); else if ( !c[to[i]] ) low[x] = min( low[x], dfn[to[i]] ); } if ( low[x] == dfn[x] ){ c[x] = ++cnt; f[cnt] = pr[x]; while( stk[tp] != x ) f[cnt] = min( f[cnt], pr[stk[tp]] ), c[stk[tp--]] = cnt; tp--; }}//记忆化搜索//Memory search void DFS( int x ){ v[x] = 1; for ( int i = hd[x]; i; i = nxt[i] ) if ( !v[to[i]] ) DFS( to[i] );}int main(){ scanf( "%d%d", &n, &p ); for ( int i = 1; i <= n; ++i ) pr[i] = INT_MAX; for ( int i = 1; i <= p; ++i ) scanf( "%d%d", &x, &y ), pr[x] = y; scanf( "%d", &r ); for ( int i = 1; i <= r; ++i ) scanf( "%d%d", &x, &y ), Add( x, y ); // 先判断是否能控制全部间谍,即把所有能收买的间谍都收买 // To see whether all spies can be under control. for ( int i = 1; i <= n; ++i ) if ( pr[i] < INT_MAX && !v[i] ) DFS( i ); for ( int i = 1; i <= n; ++i ) if ( !v[i] ){ printf( "NO\n%d\n", i ); return 0; } //------------------判断结束 Ended-------------------- //因为已经确定所有间谍都能被控制,那就大胆地取来所有入度为0的节点(当然,是缩点后的图) // Because all spies can be controled, get all ponits which has no indegree(After Tarjan, certainly). for ( int i = 1; i <= n; ++i ) if ( !c[i] ) Tarjan( i ); //当然, 并不需要建边，可以直接判断入度是否为0 //Certainly, it is unnecessary to connect edges.You can DIRECTLY know whether a point has no indegree. for ( int i = 1; i <= n; ++i ) for ( int j = hd[i]; j; j = nxt[j] ) if ( c[i] != c[to[j]] ) vs[c[to[j]]] = 1; int ans(0); for ( int i = 1; i <= cnt; ++i ) if ( !vs[i] ) ans += f[i]; printf( "YES\n%d\n", ans ); return 0;}
注：为了防止中文乱码情况，代码注释给出英文版。