题目链接：UVA-10480 Sabotage
给出一个图的连边(无向边)和割断每条边的花费，要割掉一些边令结点1和结点2不连通，求最小花费的切割方案。
在原图上以结点1为源点，结点2为汇点，边的花费为容量建立流网络，最小割即为最小花费。
设割边将流网络的结点分为$S$和$T$两个集合。Ford-Fulkerson方法求最大流后的残量网络中，从源点开始dfs，每次走残余容量大于$0$的边，即可找到所有$S$集合内的结点。所有边$(u,v)$中，若$u\in S, v\in T$，则$(u,v)$为割边。
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using std::queue; const int INF = 0x3f3f3f3f, N = 60, M = 1100; int head[N], d[N]; int s, t, tot, maxflow; bool vis[N]; struct Edge { int to, cap, nex; } edge[M]; queue<int> q; void add(int x, int y, int z) { edge[++tot].to = y, edge[tot].cap = z, edge[tot].nex = head[x], head[x] = tot; } bool bfs() { memset(d, 0, sizeof(d)); while (q.size()) q.pop(); q.push(s); d[s] = 1; while (q.size()) { int x = q.front(); q.pop(); for (int i = head[x]; i; i = edge[i].nex) { int v = edge[i].to; if (edge[i].cap && !d[v]) { q.push(v); d[v] = d[x] + 1; if (v == t) return true; } } } return false; } int dinic(int x, int flow) { if (x == t) return flow; int rest = flow, k; for (int i = head[x]; i && rest; i = edge[i].nex) { int v = edge[i].to; if (edge[i].cap && d[v] == d[x] + 1) { k = dinic(v, std::min(rest, edge[i].cap)); if (!k) d[v] = 0; edge[i].cap -= k; edge[i^1].cap += k; rest -= k; } } return flow - rest; } void init() { tot = 1, maxflow = 0; s = 1, t = 2; memset(head, 0, sizeof(head)); memset(vis, false, sizeof(vis)); } void dfs(int u) { vis[u] = true; for (int i = head[u]; i; i = edge[i].nex) { int v = edge[i].to; if (!vis[v] && edge[i].cap) dfs(v); } } int main() { int n, m; while (~scanf("%d %d", &n, &m) && (n || m)) { init(); for (int i = 0, u, v, z; i < m; i++) { scanf("%d %d %d", &u, &v, &z); add(u, v, z); add(v, u, z); } while (bfs()) maxflow += dinic(s, INF); dfs(s); for (int i = 1; i <= n; i++) { if (vis[i]) { for (int j = head[i]; j; j = edge[j].nex) { if (!vis[edge[j].to]) printf("%d %d\n", i, edge[j].to); } } } puts(""); } return 0; }
原文：https://www.cnblogs.com/kangkang-/p/11333032.html
