最小割

最小割定义

  1. 割 : 点的划分方式, 将图中的所有点划分成2个集合,源点s,汇点t, $s\in S,t \in T$.
  2. 割的容量 ： 表示所有从S到T的边的容量之和,$c(S,T) = \Sigma_{u \in S,v \in T}c(u,v)$
  3. 最小割问题: 求一个割的方法使得割的容量最小

最大流 = 最小割

  • 求最小割和最大流可以看做是一个问题

最小割例题 luogu P1344

问题

  1. 最小割的值
  2. 最小割边的个数

直接求最小割

  • 第一问直接求最大流
  • 对于第二问重新建图 将边权改为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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 50;
const int maxm = 1e4+5;
const ll inf = 1e9+1;

struct Edge{
    int v,next;
    ll c;
} edge[maxm];

int n,m,tot,source,sink;
int head[maxn],dep[maxn];

void add(int u,int v,ll c) {
    edge[tot].v=v; edge[tot].c=c;
    edge[tot].next=head[u]; head[u]=tot++;
}

void addedge(int u,int v,ll c) {
    add(u,v,c);
    add(v,u,0);
}

bool bfs() {
    queue<int> que;
    memset(dep,-1,sizeof dep);
    dep[source] = 0; // 深度标记数组
    que.push(source);
    while (!que.empty()) {
        int cur = que.front(); que.pop();
        for (int i=head[cur]; i!=-1; i=edge[i].next) {
            int to = edge[i].v;
            if (edge[i].c>0 && dep[to]==-1) {
                dep[to] = dep[cur] + 1;
                que.push(to);
            }
        }
    }
    return dep[sink] != -1;
}

ll dfs(int u,ll delta) {
    if (u == sink)
        return delta;
    ll flow = 0;
    for (int i=head[u]; i!=-1; i=edge[i].next) {
        int to = edge[i].v;
        if (edge[i].c>0 && dep[to]==dep[u]+1) {
            ll temp = dfs(to,min(delta-flow,edge[i].c));
            edge[i].c -= temp;
            edge[i^1].c += temp;
            flow += temp;
        }
    }
    if (!flow) dep[u] = -1;
    return flow;
}

ll Dinic() {
    ll ans = 0;
    while(bfs()) {
        while (1) {
            ll temp = dfs(source,inf);
            if (!temp) break;
            ans += temp;
        }
    }
    return ans;
}

struct Storage {
    int u,v;
} storage[maxm];


int main() {
    memset(head,-1,sizeof head);
    scanf("%d%d",&n,&m);
    source = 1;
    sink = n;
    for (int i=1; i<=m; ++i) {
        int u,v;
        ll c;
        scanf("%d %d %lld",&u,&v,&c);
        addedge(u,v,c);
        storage[i].u = u;
        storage[i].v = v;
    }
    ll maxflow = Dinic();
    // 重新建图求 最小割的数量

    memset(head,-1,sizeof head);
    memset(edge,0,sizeof edge);
    tot = 0;

    for (int i=1; i<=m; ++i)
        addedge(storage[i].u,storage[i].v,1);

    ll cut_count = Dinic();

    cout << maxflow << " " << cut_count << endl;
    return 0;
}

最小割转最大流

  1. 建图时边权$w=k*w+1$, 若$S$为最小割边集 则 $w_i \in S$

$w_1+w_2+w_3+…+w_n = ans$

$w_1k+w_2k+w_3k+…+w_nk = ans*k$

$(w_1k+1)+(w_2k+1)+(w_3k+1)+…+(w_nk+1) = ans*k+n = ans_1$

  • 最小割: $ans = ans_1/k$
  • 最大流: $cut=ans_1 % k$
  1. 注意long long
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 50;
const int maxm = 1e4+5;
const ll mod = 2000;
const ll inf = 1e9+1;

struct Edge {
    int v,next;
    ll c;
}edge[maxm];

int head[maxn],dep[maxn];
int n,m,tot,source,sink;

void add(int u,int v,ll c){
    edge[tot].v=v; edge[tot].c=c;
    edge[tot].next=head[u]; head[u]=tot++;
}
void addedge(int u,int v,ll c) {
    add(u,v,c);
    add(v,u,0);
}

bool bfs() {
    queue<int> que;
    memset(dep,-1,sizeof dep);
    dep[source] = 0;
    que.push(source);
    while(!que.empty()) {
        int cur = que.front(); que.pop();
        for (int i=head[cur]; i!=-1; i=edge[i].next) {
            int to = edge[i].v;
            if (edge[i].c>0 && dep[to] == -1) {
                dep[to] = dep[cur] + 1;
                que.push(to);
            }
        }
    }
    return dep[sink] != -1;
}

ll dfs(int u,int delta) {
    if (u == sink)
        return delta;
    ll flow = 0;
    for (int i=head[u]; i!=-1; i=edge[i].next) {
        int to = edge[i].v;
        if (edge[i].c>0 && dep[to]==dep[u]+1) {
            ll temp = dfs(to,min(delta-flow,edge[i].c));
            edge[i].c -= temp;
            edge[i^1].c += temp;
            flow += temp;
        }
    }
    if (!flow) dep[u] = -1;
    return flow;
}

ll Dinic() {
    ll ans=0;
    while (bfs()) {
        while(1) {
            ll temp = dfs(source,inf);
            if (!temp) break;
            ans += temp;
        }
    }
    return ans;
}

int main() {
    memset(head,-1,sizeof head);
    scanf("%d%d",&n,&m);
    for (int i=1; i<=m; ++i) {
        int u,v;
        ll c;
        scanf("%d%d%lld",&u,&v,&c);
        addedge(u,v,c*mod+1);
    }
    source = 1;
    sink = n;
    ll ans = Dinic();
    cout << ans/mod << " " << ans%mod << endl;
    return 0;
}
  • 2019/11/18 0:36:23 真晚
算法
最小割

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！