题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=7244
杭电题解：先让 1号选手赢下所有和他有关的比赛，设此时选手赢了a场比赛。如果存在某个 ai> a1 则1号选手不可能成为冠军。否则选手至多还能再赢bi = a1 - ai 场比赛。考虑建立一张网络流图: 每场未进行的比赛在图中用一个点表示，源点向它连容量为 1的边，它向它的两个参赛选手的对应点各自连容量为 1的边，选手的对应点向汇点连容量为 bi 的边。计算该图最大流，若源点出发的边满流则答案为 YES ，否则为 NO。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define el '\n' 4 using ll = long long; 5 using db = double; 6 using ldb = long double; 7 const int mod = 1e9 + 7; 8 const int inf = 0x3f3f3f3f; 9 const int N = 2000 + 10; 10 const int M = 10000 + 10; 11 12 int lv[N], cur[N], head[N]; 13 int n, m, s, t, tot; 14 15 struct node { 16 int to, next, w; 17 }e[M]; 18 19 void add(int u, int v, int w) { 20 e[tot].to = v; 21 e[tot].w = w; 22 e[tot].next = head[u]; 23 head[u] = tot++; 24 } 25 26 inline bool bfs() { 27 memset(lv, -1, sizeof(lv)); 28 memcpy(cur, head, sizeof(head)); 29 queue<int>q; 30 q.push(s); 31 lv[s] = 0; 32 while (!q.empty()) { 33 int p = q.front(); 34 q.pop(); 35 for (int i = head[p]; i + 1; i = e[i].next) { 36 int to = e[i].to, vol = e[i].w; 37 if (vol > 0 && lv[to] == -1) { 38 lv[to] = lv[p] + 1; 39 q.push(to); 40 } 41 } 42 } 43 return lv[t] != -1; 44 } 45 46 int dfs(int p = s, int flow = inf) { 47 if (p == t) 48 return flow; 49 int rmn = flow; 50 for (int i = cur[p]; i + 1 && rmn; i = e[i].next) { 51 cur[p] = i; 52 int to = e[i].to, vol = e[i].w; 53 if (vol > 0 && lv[to] == lv[p] + 1) { 54 int c = dfs(to, min(rmn, vol)); 55 rmn -= c; 56 e[i].w -= c; 57 e[i ^ 1].w += c; 58 } 59 } 60 return flow - rmn; 61 } 62 63 inline ll dinic() { 64 ll ans = 0; 65 while (bfs()) { 66 ans += dfs(); 67 } 68 return ans; 69 } 70 71 int a[N]; 72 73 int main() { 74 75 ios::sync_with_stdio(false); 76 cin.tie(0), cout.tie(0); 77 int T; 78 cin >> T; 79 t = 2000, s = 0; 80 while (T--) { 81 int n, m1, m2, cnt, sum = 0; 82 cin >> n >> m1 >> m2; 83 memset(head, -1, sizeof(head)); 84 memset(e, 0, sizeof(e)); 85 memset(a, 0, sizeof(a)); 86 tot = 0, cnt = n; 87 int mx = 0; 88 for (int i = 1; i <= m1; i++) { 89 int u, v, f; 90 cin >> u >> v >> f; 91 if (f) a[u] ++; 92 else a[v] ++; 93 mx = max(mx, max(a[u], a[v])); 94 } 95 for (int i = 1; i <= m2; i++) { 96 int u, v; 97 cin >> u >> v; 98 if (u == 1 || v == 1) { a[1] ++; continue; } 99 sum ++; 100 add(s, ++cnt, 1), add(cnt, s, 0); 101 add(cnt, u, 1), add(u, cnt, 0); 102 add(cnt, v, 1), add(v, cnt, 0); 103 } 104 if (sum == 0) { 105 if (a[1] >= mx) cout << "YES" << el; 106 else cout << "NO" << el; 107 continue; 108 } 109 if (mx > a[1]) { cout << "NO" << el; continue; } 110 for (int i = 2; i <= n; i++) { 111 if (a[1] >= a[i]) add(i, t, a[1] - a[i]), add(t, i, 0); 112 } 113 int ansf = dinic(); 114 if (ansf == sum) cout << "YES" << el; 115 else cout << "NO" << el; 116 } 117 118 return 0; 119 }