HDU6214 (Smallest Minimum Cut)[网络流，最小割边数最小]

发表于 | 更新于 | | 阅读次数：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6214

题目要求求出最小割的最少割边数。
可以理解为双关键字网络流，把每条边容量变成cap*(E+1)+1，E为边集大小（当然E+1也可以是任一个大于边集+1的数），跑一遍最大流。
最小割即为maxflow/(E+1)
最小割边数为maxflow%(E+1) （可以这样理解，一条边是割边当且仅当它被取满，此时这条边容量中新加入的那个1也会被取走）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=209;
const int M=2009;
const int inf=0x7fffffff;
const int B=1000000;
int d[N],head[N],e[M],next2[M],ver[M];
int s,t,m,n,tot=1,maxflow=0;
void add(int u,int v,int w) {
    ver[++tot]=v;e[tot]=w;next2[tot]=head[u];head[u]=tot;
    ver[++tot]=u;e[tot]=0;next2[tot]=head[v];head[v]=tot;
}
bool bfs() {
    queue<int> q;
    memset(d,0,sizeof(d));
    q.push(s);
    d[s]=1;
    while(!q.empty()) {
        int x=q.front(); q.pop();
        for(int i=head[x];i;i=next2[i]) {
            if(e[i] && !d[ver[i]]) {
                q.push(ver[i]);
                d[ver[i]]=d[x]+1;
                if(ver[i]==t) return 1;
            }
        }
    }
    return 0;
}

int dinic(int x,int f) {
    int rest=f;
    if(x==t) return f;
    for(int i=head[x];i&&rest;i=next2[i]){
        if(e[i] && d[ver[i]]==d[x]+1) {
            int now=dinic(ver[i],min(e[i],rest));
            if(!now) d[ver[i]]=0;
            e[i]-=now;
            e[i^1]+=now;
            rest-=now;
        }
    }
    return f-rest;
}

int main() {
    int T;
    int u,v,w;
    scanf("%d",&T);
    while(T--) {
        tot=1;
        maxflow=0;
        memset(head,0,sizeof(head));
        scanf("%d%d",&n,&m);
        scanf("%d%d",&s,&t);
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w*(m+1)+1);
        }
        int tmp=0;
        while(bfs())
            while(tmp=dinic(s,inf)) maxflow+=tmp;
        printf("%d\n",maxflow%(m+1));
    }
}