由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。
我们的反间谍机关提供了一份资料，色括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有n个间谍(n不超过3000)，每个间谍分别用1到3000的整数来标识。
请根据这份资料，判断我们是否有可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。
第一行只有一个整数n。
第二行是整数p。表示愿意被收买的人数，1≤p≤n。
接下来的p行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过20,000。
紧跟着一行只有一个整数r，1≤r≤8000。然后r行，每行两个正整数，表示数对(A, B)，A间谍掌握B间谍的证据。
如果可以控制所有间谍，第一行输出YES，并在第二行输出所需要支付的贿金最小值。否则输出NO，并在第二行输出不能控制的间谍中，编号最小的间谍编号。
2 1 2 512 2 1 2 2 1
YES 512
强连通分量+Tar缩点，只要找出每个强连通分量中价值最小的点即可，最后找入度为0的点即可，入度为0就说明必须收买。
#include<bits/stdc++.h> using namespace std; const int maxn = 3e3+5; const int inf = 0x3f3f3f3f; int low[maxn],dfn[maxn],Stack[maxn]; int in[maxn],val[maxn],t[maxn],minval[maxn]; bool instack[maxn],vis[maxn]; int tot,cnt,num,n,p,r; vector<int>e[maxn]; void Tar(int u) { low[u] = dfn[u] = ++tot; Stack[++num] = u; instack[u] = true; for(int i = 0 ; i < e[u].size() ; i++) { int v = e[u][i]; if(!dfn[v]) { Tar(v); low[u] = min(low[u],low[v]); } else if(instack[v]) { low[u] = min(low[u],dfn[v]); } } if(dfn[u] == low[u]) { while(u != Stack[num]) { minval[cnt] = min(minval[cnt],val[Stack[num]]); t[Stack[num]] = cnt; instack[Stack[num]] = false; num--; } minval[cnt] = min(minval[cnt],val[Stack[num]]); t[Stack[num]] = cnt; instack[Stack[num]] = false; num--; cnt++; } } int main() { fill(minval,minval+maxn,inf); cin >> n >> p; for(int i = 0 ; i < p ; i++) { int u,w; cin >> u >> w; val[u] = w; vis[u] = true; } cin >> r; for(int i = 0 ; i < r ; i++) { int u,v; cin >> u >> v; if(vis[u]) { e[u].push_back(v); } vis[v] = true; } for(int i = 1 ; i <= n ; i++) { if(vis[i] == false) { cout << "NO\n" << i << endl; return 0; } } for(int i = 1 ; i <= n ; i++) { if(!dfn[i]) Tar(i); } for(int i = 1 ; i <= n ; i++) { for(int j = 0 ; j < e[i].size() ; j++) { int u = i,v = e[u][j]; if(t[u] != t[v]) { in[t[v]]++; } } } int ans = 0; for(int i = 0 ; i < cnt ; i++) { if(!in[i] && minval[i] != inf) ans += minval[i]; } cout << "YES\n" << ans << endl; return 0; }