题意：一个英雄，分到几个城市，每个城市有一个价值，但是要求分到城市后，必须破坏掉道路使得首都1都不能到达，破坏道路有开销，问最大能获得的收益和需要破坏的道路ID

思路：最小割，城市1做源点，有向边建图，容量为代价，然后每个可以分的城市连到汇点，容量为价值，跑一下最小割即可

代码：

[cpp] view plaincopy

1. #include <cstdio>  
2. #include <cstring>  
3. #include <queue>  
4. #include <algorithm>  
5. using namespace std;  
6.   
7. const int MAXNODE = 1005;  
8. const int MAXEDGE = 300005;  
9.   
10. typedef int Type;  
11. const Type INF = 0x3f3f3f3f;  
12.   
13. struct Edge {  
14.     int u, v, id;  
15.     Type cap, flow;  
16.     Edge() {}  
17.     Edge(int u, int v, Type cap, Type flow, int id) {  
18.         this->u = u;  
19.         this->v = v;  
20.         this->cap = cap;  
21.         this->flow = flow;  
22.         this->id = id;  
23.     }  
24. };  
25.   
26. struct Dinic {  
27.     int n, m, s, t;  
28.     Edge edges[MAXEDGE];  
29.     int first[MAXNODE];  
30.     int next[MAXEDGE];  
31.     bool vis[MAXNODE];  
32.     Type d[MAXNODE];  
33.     int cur[MAXNODE];  
34.     vector<int> cut;  
35.   
36.     void init(int n) {  
37.         this->n = n;  
38.         memset(first, -1, sizeof(first));  
39.         m = 0;  
40.     }  
41.     void add_Edge(int u, int v, Type cap, int id) {  
42.         edges[m] = Edge(u, v, cap, 0, id);  
43.         next[m] = first[u];  
44.         first[u] = m++;  
45.         edges[m] = Edge(v, u, 0, 0, id);  
46.         next[m] = first[v];  
47.         first[v] = m++;  
48.     }  
49.   
50.     bool bfs() {  
51.         memset(vis, false, sizeof(vis));  
52.         queue<int> Q;  
53.         Q.push(s);  
54.         d[s] = 0;  
55.         vis[s] = true;  
56.         while (!Q.empty()) {  
57.             int u = Q.front(); Q.pop();  
58.             for (int i = first[u]; i != -1; i = next[i]) {  
59.                 Edge& e = edges[i];  
60.                 if (!vis[e.v] && e.cap > e.flow) {  
61.                     vis[e.v] = true;  
62.                     d[e.v] = d[u] + 1;  
63.                     Q.push(e.v);  
64.                 }  
65.             }  
66.         }  
67.         return vis[t];  
68.     }  
69.   
70.     Type dfs(int u, Type a) {  
71.         if (u == t || a == 0) return a;  
72.         Type flow = 0, f;  
73.         for (int &i = cur[u]; i != -1; i = next[i]) {  
74.             Edge& e = edges[i];  
75.             if (d[u] + 1 == d[e.v] && (f = dfs(e.v, min(a, e.cap - e.flow))) > 0) {  
76.                 e.flow += f;  
77.                 edges[i^1].flow -= f;  
78.                 flow += f;  
79.                 a -= f;  
80.                 if (a == 0) break;  
81.             }  
82.         }  
83.         return flow;  
84.     }  
85.   
86.     Type Maxflow(int s, int t) {  
87.         this->s = s; this->t = t;  
88.         Type flow = 0;  
89.         while (bfs()) {  
90.             for (int i = 0; i < n; i++)  
91.                 cur[i] = first[i];  
92.             flow += dfs(s, INF);  
93.         }  
94.         return flow;  
95.     }  
96.   
97.     void MinCut() {  
98.         cut.clear();  
99.         for (int i = 0; i < m; i += 2) {  
100.             if (vis[edges[i].u] && !vis[edges[i].v] && edges[i].id)  
101.                 cut.push_back(i);  
102.         }  
103.         int sz = cut.size();  
104.         printf("%d", sz);  
105.         for (int i = 0; i < sz; i++)  
106.             printf(" %d", edges[cut[i]].id);  
107.         printf("\n");  
108.     }  
109. } gao;  
110.   
111. int t, n, m, f;  
112.   
113. int main() {  
114.     int cas = 0;  
115.     scanf("%d", &t);  
116.     while (t--) {  
117.         scanf("%d%d%d", &n, &m, &f);  
118.         gao.init(n + 1);  
119.         int u, v, w, tot = 0;  
120.         for (int i = 1; i <= m; i++) {  
121.             scanf("%d%d%d", &u, &v, &w);  
122.             gao.add_Edge(u, v, w, i);  
123.         }  
124.         while (f--) {  
125.             scanf("%d%d", &u, &w);  
126.             tot += w;  
127.             gao.add_Edge(u, 0, w, 0);  
128.         }  
129.         printf("Case %d: %d\n", ++cas, tot - gao.Maxflow(1, 0));  
130.         gao.MinCut();  
131.     }  
132.     return 0;  
133. } 

HDU 3215 Being a Hero（最小割）