P1262

间谍a知道间谍b的情报，那么a向b连边，比较显然的做法就是用tarjan先缩点，这样一个联通块中只要一个人被抓捕，其他的都能抓捕，我们对于每个连通块维护块内的最小花费，再维护块内最小的节点编号。

对于入度为0的连通块我们肯定是需要购买的，购买后他所连向的连通块我们就都可以抓捕了，依次下去。所以我们可以标记一个连通块是否有入度，最后扫描所有连通块时有入度就直接跳过，没入度时如果判断到无解就输出最小节点编号，有解则累加花费，最后输出即可。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 10010, inf = 1e9 + 10;
 4 int n, p, t, idx;
 5 int w[N], dfn[N], low[N];
 6 int minw[N], minid[N], bel[N];
 7 bool vis[N], flag[N][N], ru[N];
 8 //flag[i][j]连通块i连向j  ru[i]连通块i有入度 
 9 vector<int> e[N];
10 stack<int> s;
11 void tarjan(int x) {
12     low[x] = dfn[x] = ++ t;
13     s.push(x), vis[x] = 1;
14     for (int i = 0; i < e[x].size(); i ++) {
15         int y = e[x][i];
16         if (!dfn[y]) {
17             tarjan(y);
18             low[x] = min(low[x], low[y]);
19         }
20         else if (vis[y])
21             low[x] = min(low[x], dfn[y]);
22     }
23     if (dfn[x] == low[x]) {
24         idx ++;
25         int v, W = inf, D = inf;
26         do {
27             v = s.top();
28             s.pop();
29             vis[v] = 0;
30             W = min(W, w[v]); // 维护连通块最小花费
31             D = min(D, v);// 维护连通块最小节点编号 
32             bel[v] = idx;
33         } while (v != x);
34         minw[idx] = W, minid[idx] = D;
35     }
36 }
37 int main() {
38     ios::sync_with_stdio(false);
39     cin.tie(0), cout.tie(0);
40     cin >> n >> p;
41     for (int i = 1; i <= n; i ++) w[i] = inf;
42     int a, b;
43     while (p --) {
44         cin >> a >> b;
45         w[a] = b;
46     }
47     int r; cin >> r;
48     while (r --) {
49         cin >> a >> b;
50         e[a].push_back(b);
51     }
52     for (int i = 1; i <= n; i ++) 
53         if (!dfn[i]) tarjan(i);
54     for (int i = 1; i <= n; i ++) {
55         for (int j = 0; j < e[i].size(); j ++) {
56             int y = e[i][j];
57             if (bel[i] == bel[y] || flag[bel[i]][bel[y]]) continue;
58             flag[bel[i]][bel[y]] = 1;
59             if (ru[bel[i]] || minw[bel[i]] != inf) ru[bel[y]] = 1;
60             //bel[i]有入度，bel[y]肯定也有入度
61             //bel[i]可以购买，那么bel[y]也有入度 
62         }
63     }
64     int id = inf, all = 0;
65     bool f = 0;
66     for (int i = 1; i <= idx; i ++) {
67         if (ru[i]) continue;
68         if (minw[i] == inf) {//其他连通块不能到达i且i不能购买，则无解 
69             f = 1; 
70             id = min(id, minid[i]);
71         }
72         if (!f) all += minw[i];
73     }
74     if (f) printf("NO\n%d", id);
75     else printf("YES\n%d", all);
76     return 0;
77 }