P1262 间谍网络
题目描述
由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果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：
3
2
1 10
2 100
2
1 3
2 3
输出样例#1：
YES
110
输入样例#2：
4
2
1 100
4 200
2
1 2
3 4
输出样例#2：
NO
3
算法
缩点
思路
如果A掌握B的信息，那么我们就建有向边A->B，构成一个图。
每个点的权值就是收买该间谍需要花的钱，如果不能收买，那就赋为(infty)。
我们的任务就是取Sum(点权)最少的若干个点，以这几个点为起点，能遍历整张图。
当然，Sum(点权)不能为(infty)。（注意下 (infty + infty = infty ,infty + x = infty)）
因为在一个强连通分量中，任何一个点都能遍历到每个节点。所以，对于一个强连通分量，完全可以看成一个点，点权为该强连通分量包含的点的最小点权。
所以缩点即可。以下所说的点均为“缩”过的点。
入度为0的点绝对要取，而取来后绝对已经所有点都能访问到。
这个很好证明。入度为0的点绝对要取是不难理解的，因为它不可能被其他点访问。由于缩点后的图不可能构成环，所以入度不为0的点肯定可以被已经访问过的点访问到。
注意下不能被控制的(编号最小)点不一定入度为0。
如这组数据:
Input Data
4
1
4 100
4
2 4
2 1
4 3
1 3
Output Data
NO
1
代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 3005
#define MAXM 8005
int 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
%d
", 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
%d
", ans );
return 0;
}
注：为了防止中文乱码情况，代码注释给出英文版。