本文共 3451 字，大约阅读时间需要 11 分钟。

题意：给一个n点m条边的无向图，现在要删掉一些边使得点1、2不连通，每条边有一个花费，问如何删边

思路：显而易见求最小割，也就是最大流，主要是如何输出路径

引用自

最小割，就是在所有割中，容量之和最小的割。最小割的值就是最大流的值，因为很容易想到，从源点s到汇点t的最大流必然会经过割边，那么就有最大流f<=c(割边的值），那么也就是说，当c==f的时候，就是c为小割，即最大流==最小割

在跑完最大流后的残余网络上，记录源点和汇点可达的点，然后遍历所有的边（设边的两端点为 u 和 v），如果 u 可达源点而 v 可达汇点（或与之相反，v 可达源点而 u 可达汇点），则说明该边必须割。

#include 
   
    using namespace std;typedef long long ll;const int inf = 0x3f3f3f3f;const int N = 55;const int M = 2005;int flag[N];int head[N], dis[N], tot, n, m, maxflow;struct Edge {    int from, to, next, cap, flow;}edge[M];void init() {    tot = 2;    memset(head, -1, sizeof(head));    memset(flag, 0, sizeof(flag));}//rw为反向流量，单向边addedge(u, v, w)//双向边时正反向流量相同可直接addedge(u, v, w, w)//双向边若加两条边（憨批操作）addedge(u, v, w), addedge(v, u, w), 输出路径时要注意每次+4，即for(int i = 0; i < tot; i += 4)void addedge(int u, int v, int w, int rw = 0) {    edge[tot].from = u;    edge[tot].to = v;    edge[tot].cap = w;    edge[tot].flow = 0;    edge[tot].next = head[u];    head[u] = tot++;    edge[tot].from = v;    edge[tot].to = u;    edge[tot].cap = rw;    edge[tot].flow = 0;    edge[tot].next = head[v];    head[v] = tot++;}int Q[N];int dep[N], cur[N], sta[N]; ///数组cur记录点u之前循环到了哪一条边bool bfs(int s, int t, int n) {    int fron = 0, tail = 0;    memset(dep, -1, sizeof(dep[0]) * (n + 1));    dep[s] = 0;    Q[tail++] = s;    while(fron < tail) {        int u = Q[fron++];        for(int i = head[u]; i != -1; i = edge[i].next) {            int v = edge[i].to;            if(edge[i].cap > edge[i].flow && dep[v] == -1) {                dep[v] = dep[u] + 1;                if(v == t) return true;                Q[tail++] = v;            }        }    }    return false;}void dinic(int s, int t, int n) {    //源点 汇点 点数    maxflow = 0;    while(bfs(s, t, n)) {        for(int i = 0; i <= n; ++i) cur[i] = head[i];        int u = s, tail = 0;        while(cur[s] != -1) {            if(u == t) {                int tp = inf;                for(int i = tail - 1; i >= 0; --i)                    tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);                maxflow += tp;                for(int i = tail - 1; i >= 0; --i) {                    edge[sta[i]].flow += tp;                    edge[sta[i] ^ 1].flow -= tp;                    if(edge[sta[i]].cap - edge[sta[i]].flow == 0)                        tail = i;                }                u = edge[sta[tail] ^ 1].to;            }            else if(cur[u] != -1 && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to]) {                sta[tail++] = cur[u];                u = edge[cur[u]].to;            }            else {                while(u != s && cur[u] == -1)                    u = edge[sta[--tail] ^ 1].to;                cur[u] = edge[cur[u]].next;            }        }    }}void dfs(int u, int op) {    flag[u] = op;    for(int i = head[u]; ~i; i = edge[i].next) {        if(edge[i].flow == edge[i].cap) continue;        int v = edge[i].to;        if(!flag[v]) dfs(v, op);    }}int main(){//    freopen("in.txt", "r", stdin);    while(~scanf("%d%d", &n, &m) && n + m) {        init();        int u, v, w;        while(m--) {            scanf("%d%d%d", &u, &v, &w);            addedge(u, v, w, w);        }        dinic(1, 2, n);        dfs(1, 1);        dfs(2, 2);        for(int i = 0; i < tot; i += 2) {            int u = edge[i].from, v = edge[i].to;            if(flag[u] + flag[v] == 3)                printf("%d %d\n", u, v);        }        printf("\n");    }	return 0;}