看着这道题给人感觉就是tarjan求SCC，然而还得判断是否能控制全部间谍，这就得先从可以贿赂的点dfs一遍。
如果没有全部被标记了，就输出NO，再从没被标记的点里找最小的标号。
如果全被标记，就输出YES，再从入度为0的缩点里找最小的价格，加到ans中，最后输出ans。
——代码
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 int n, p, r1, cnt, idx, ans = 30000001, minn; 8 int a[3001], next[8001], to[8001], head[3001], low[3001], dfn[3001], belong[3001], r[3001]; 9 bool ins[3001], vis[3001], mey[3001]; 10 stack s; 11 12 inline void add(int x, int y) 13 { 14 to[cnt] = y; 15 next[cnt] = head[x]; 16 head[x] = cnt++; 17 } 18 19 void dfs(int u) 20 { 21 int i, v; 22 vis[u] = 1; 23 mey[u] = 1; 24 for(i = head[u]; i != -1; i = next[i]) 25 { 26 v = to[i]; 27 if(!vis[v]) dfs(v); 28 } 29 } 30 31 void tarjan(int u) 32 { 33 low[u] = dfn[u] = ++idx; 34 s.push(u); 35 ins[u] = 1; 36 int i, v; 37 for(i = head[u]; i != -1; i = next[i]) 38 { 39 v = to[i]; 40 if(!dfn[v]) 41 { 42 tarjan(v); 43 low[u] = min(low[u], low[v]); 44 } 45 else if(ins[v]) low[u] = min(low[u], dfn[v]); 46 } 47 if(low[u] == dfn[u]) 48 { 49 cnt++; 50 do 51 { 52 v = s.top(); 53 s.pop(); 54 ins[v] = 0; 55 belong[v] = cnt; 56 }while(u != v); 57 } 58 } 59 60 int main() 61 { 62 int i, j, k, x, y, u, v; 63 scanf("%d %d", &n, &p); 64 for(i = 1; i <= p; i++) 65 { 66 scanf("%d", &x); 67 scanf("%d", &a[x]); 68 } 69 memset(head, -1, sizeof(head)); 70 scanf("%d", &r1); 71 for(i = 1; i <= r1; i++) 72 { 73 scanf("%d %d", &x, &y); 74 add(x, y); 75 } 76 for(i = 1; i <= n; i++) 77 if(!vis[i] && a[i]) 78 dfs(i); 79 for(i = 1; i <= n; i++) 80 if(!mey[i]) 81 ans = min(ans, i); 82 if(ans != 30000001) 83 { 84 printf("NO\n%d", ans); 85 return 0; 86 } 87 cnt = 0; 88 for(i = 1; i <= n; i++) 89 if(!dfn[i]) 90 tarjan(i); 91 for(u = 1; u <= n; u++) 92 for(i = head[u]; i != -1; i = next[i]) 93 { 94 v = to[i]; 95 if(belong[u] != belong[v]) r[belong[v]]++; 96 } 97 ans = 0; 98 for(i = 1; i <= cnt; i++) 99 if(r[i] == 0)100 {101 minn = 30000001;102 for(j = 1; j <= n; j++)103 if(belong[j] == i && a[j])104 minn = min(minn, a[j]);105 ans += minn;106 }107 printf("YES\n%d", ans);108 return 0;109 }