tarjan求强联通分量，每个强联通分量内的间谍可以互相揭发，缩点
跑拓扑排序，每个间谍（强连通分量）只可能被拓扑排序比他小的揭发
扫一遍，没被控制的收买一下，收买不了输出no.(代码实现的时候有些区别，这样也是对的）
#include <bits/stdc++.h>
using namespace std;
int low[5000], color[5000], cnt = 0, w[5000], uu[50000], vv[50000], cover[5000], rd[5000], line[5000], lc = 0,
ww[5000], colornum = 0, dfn[5000], t = 0, sta[5000], stac = 0,
in[5000], head[5000];
struct node {
int to, nxt;
} road[10000];
void build(int u, int v)
{
road[++cnt].to = v;
road[cnt].nxt = head[u];
head[u] = cnt;
}
void tarjan(int u)
{
low[u] = dfn[u] = ++t;
in[u] = 1, sta[++stac] = u;
for (int i = head[u]; i; i = road[i].nxt)
{
int v = road[i].to;
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
color[u] = ++colornum, in[u] = 0;
if (w[u] != -1)
ww[colornum] = w[u];
while (sta[stac] != u)
{
in[sta[stac]] = 0;
if (w[sta[stac]] != -1)
{
if (ww[colornum] == -1)
ww[colornum] = w[sta[stac]]; // QAQ
else
ww[colornum] = min(ww[colornum], w[sta[stac]]);
}
color[sta[stac]] = colornum;
stac--;
}
stac--;
}
}
int ans = 0;
void tuopu(int u) {
line[++lc] = u;
for (int i = head[u]; i; i = road[i].nxt) {
int v = road[i].to;
rd[v]--;
if (!rd[v])
tuopu(v);
}
}
void dfs(int u) {
cover[u] = 1;
for (int i = head[u]; i; i = road[i].nxt) {
int v = road[i].to;
if (!cover[v])
dfs(v);
}
}
int main() {
memset(w, -1, sizeof(w));
memset(ww, -1, sizeof(ww));
int n, p, r, u, v, ans = 0;
cin >> n >> p;
for (int i = 1; i <= p; i++) {
int x;
cin >> x;
cin >> w[x];
}
cin >> r;
for (int i = 1; i <= r; i++) {
cin >> uu[i] >> vv[i];
build(uu[i], vv[i]);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
tarjan(i);
}
}
memset(head, 0, sizeof(head));
cnt = 0;
for (int i = 1; i <= r; i++) {
if (color[uu[i]] != color[vv[i]]) {
build(color[uu[i]], color[vv[i]]);
rd[color[vv[i]]]++;
}
}
for (int i = 1; i <= colornum; i++) {
if (!rd[i])
tuopu(i);
}
for (int i = 1; i <= lc; i++) {
if (!cover[line[i]] && ww[line[i]] != -1) {
ans += ww[line[i]];
dfs(line[i]);
}
}
int f = 0;
for (int i = 1; i <= n; i++) //直接循环强联通分量 不能保证编号最小
// 循环的顺序是按编号从小到大，但是实际最先成为强联通分量，可能是编号较大的某个儿子
{
if (!cover[color[i]]) {
f = 1;
cout << "NO"<<"
"<< i;
break; // QAQ
}
}
if (f == 0)
cout << "YES"
<< "
"
<< ans;
return 0;
}