网络流二十四题

ACM

说明：不刷完题目不更新博客 (可能永远不会更新了\吐血而亡)
2018年1月20日14:33:43更新

最大流模板

题目链接

poj1273 Drainage Ditches

题解

先bfs求出最短的层次图，然后dfs拓展增广路。不断的缩小拓展的增广路。

AC代码

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
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 205;
const int INF = 1e9+10;
struct Edge{
    int to, cap, rev;
};
vector<Edge> G[maxn];
int n, m;
void add_edge(int u, int v, int cap){
    G[u].push_back(Edge{v, cap, G[v].size()});//指向v节点所连接的边的在v的vector中的序号，可以手动的模拟一下。
    G[v].push_back(Edge{u, 0, G[u].size()-1});//因为一开始加入了一条边，所以减1。
}
int level[maxn];
int cnt[maxn];
//构造层次图
void bfs(int s){
    queue<int> q;
    q.push(s);
    level[s] = 0;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int i=0; i<G[v].size(); i++){
            Edge& e = G[v][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to] = level[v]+1;
                q.push(e.to);
            }
        }
    }
}
int dfs(int v, int t, int flow){
    if(v == t) return flow;
    for(int& i=cnt[v]; i<G[v].size(); i++){
        Edge& e = G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d = dfs(e.to, t, min(flow, e.cap));
            //printf("dis:%d->%d %d %d %d\n", v, e.to, e.cap, flow, d);
            if(d>0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    //无到t的增广路，直接返回0。
    return 0;//等价于返回0
}
int max_flow(int s, int t){
    int flow = 0;
    int tot = 0;
    for(;;){
        memset(level, -1, sizeof(level));
        bfs(s);
        for(int i=1; i<=n; i++){
            //printf("%d: %d\n", i, level[i]);
        }
        //无法连通t，返回结果。
        if(level[t]<0) return flow;
        int f;
        memset(cnt, 0, sizeof(cnt));
        while((f=dfs(s, t, INF))>0){
            //printf("test:%d: %d\n", ++tot, f);
            flow+=f;
        }
    }
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        int u, v, weight;
        for(int i=0; i<m; i++) G[i].clear();
        for(int i=0; i<n; i++){
            scanf("%d%d%d", &u, &v, &weight);
            add_edge(u, v, weight);
        }
        int s = 1;
        int t = m;
        printf("%d\n", max_flow(s, t));
    }
    return 0;
}

最小费流模板题

poj2135 Farm Tour

题意

从一个点出发到达终点后返回起始点，每个边最多经过一次，并且每条边有一个长度。问访问的最小长度。
保证有这样的路径存在。
图一开始是无向图。

题解

  • 建立一个源点和一个汇点。源点连向1节点，费用为0， 容量为2.同理，最后一个节点n向汇点连接一条边，费用为0， 容量为2.
  • 图中的两点间的费用就是距离，容量为1（因为每条边最多经过一次）.
  • 建立双向边，因为是无向图。

AC代码

说明：
这里面的流量是固定的，不一定是最大流量。
里面先是用BF算法跑一边最短路（最短路的属性是价格）（因为存在负边，所以不能用dijkstra来更新）。然后找到这条路径上的最小的容量，并且减掉。
里面用的是最朴素的BF算法，因此还可以用堆来进行优化。

《挑程》里面引入了势的概念，可以进一步的优化算法。 
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
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int n, m;
const int maxn = 1e3+10;
const int INF = 1e9+10;
struct Edge{
    int to, cap, cost, rev;
};
vector<Edge> G[maxn];
int dis[maxn];
int prev[maxn], pree[maxn];
void add_edge(int u, int v, int cap, int cost){
    G[u].push_back(Edge{v, cap, cost, G[v].size()});
    G[v].push_back(Edge{u, 0, cost*(-1), G[u].size()-1});
}
int min_cost_flow(int s, int t, int f){
    int res = 0;
    while(f>0){
        fill(dis, dis+maxn, INF);
        dis[s] = 0;
        bool update = true;
        while(update){
            update = false;
            for(int v=0; v<=n; v++){
                if(dis[v] == INF) continue;
                for(int i=0; i<G[v].size(); i++){
                    Edge& e = G[v][i];
                    if(e.cap>0&&dis[e.to] > dis[v]+e.cost){
                        dis[e.to] = dis[v]+e.cost;
                        prev[e.to] = v;
                        pree[e.to] = i;
                        update = true;
                    }
                }
            }
        }
        if(dis[t] == INF) return -1;
        int d = f;
        for(int v = t; v!=s; v = prev[v]){
            d = min(d, G[prev[v]][pree[v]].cap);
        }
        f -= d;
        res += d*dis[t];
        for(int v = t; v!=s; v = prev[v]){
            Edge& e = G[prev[v]][pree[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;//e.rev是prev[v]和v之间的连边的逆向边，在v节点中的序号。可以画一张图进行理解。
        }
    }
    return res;
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        for(int i=0; i<=n+1; i++) G[i].clear();
        int u, v, cost;
        int s=0;
        int t = n+1;
        add_edge(s, 1, 2, 0);
        add_edge(n, t, 2, 0);
        for(int i=0; i<m; i++){
            scanf("%d%d%d", &u, &v, &cost);
            add_edge(u, v, 1, cost);
            add_edge(v, u, 1, cost);
        }
        printf("%d\n", min_cost_flow(s, t, 2));
    }
    return 0;
}

最大流

poj3436 ACM computer factory

题意

现在N个人，他们的电脑都有P个输入部分和P个输出部分。
输入部分：
P个输入部分，它们可以用0,1,2三个数字来表示状态：

  • 0表示肯定是没有这个部分的
  • 1表示肯定是有这个部分的
  • 2表示这个部分可有可无

P个输出部分：

  • 0表示一定没有这个部分
  • 1表示一定是有这个部分

每一个电脑有一个权重W，表示这个电脑可以传输的最大的价值。

题目要求这些电脑之间进行传输，使得传输的价值最大，并且输出相应的传输的路径，和他们之间的权值。
因为有多解，因此输出任意的解即可。

题解

  1. 首先进行拆点操作，每一个电脑拆成两个点，这两个点之间的传输容量(cap)为每一个电脑的权重
  2. 若一个电脑的P个输入和为0，那么将一个超级源和它相连，并且它们之间的传输容量为INF；若一个电脑的输出圈为0，那么它的拆分的第二个点和超级汇相连。
  3. 若两个电脑C1, C2,C1的输入能接上C2的输出，那么C2所拆的第二个点和C1的第一个点相连。同理，若C2的输入和C1的输出可以连上，那么也可以建边。这些边的容量都是INF
  4. 从超级源向超级汇跑一边最大流即可。
    注意体会拆点的思想，以及两个电脑建边的时候的容量设为INF的思想。

代码

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 60*2;
const int max_in = 12;
int level[maxn];
int from[maxn], to[maxn], flow[maxn], cap[maxn];
int head[maxn], nex[maxn], cnt[maxn];
int P, N;
int s, t;
int e = 0;
void add_edge(int u, int v, int weight1){
    //从0开始存边
    from[e] = u, to[e] = v, cap[e] = weight1, nex[e] = head[u], head[u] = e;
    e++;
    from[e] = v, to[e] = u, cap[e] = 0, nex[e] = head[v], head[v] = e;
    e++;
    return;
}
int bfs(int s){
    queue<int> q;
    while(!q.empty()) q.pop();
    memset(level, -1, sizeof(level));
    level[s] = 0;
    q.push(s);
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        for(int e=head[temp]; e!=-1; e=nex[e]){
            //printf("%d\n", e);
            if(cap[e]>flow[e]&&level[to[e]]<0){
                level[to[e]] = level[temp] + 1;
                q.push(to[e]);
            }
        }
    }
}
int dfs(int u ,int t, int f){
    if(u == t) return f;
    for(int& e = cnt[u]; e!=-1; e=nex[e]){
        if(cap[e]>flow[e] && level[from[e]]<level[to[e]]){
            int d = dfs(to[e], t, min(f, cap[e]-flow[e]));
            if(d>0){
                flow[e] += d;
                flow[e^1] -= d;
                return d;
            }
        }
    }
    return 0;
}
int max_flow(int s, int t){
    int flow = 0;
    for(;;){
        bfs(s);
//        for(int i=0; i<=2*N+1; i++){
//            printf("%d ", level[i]);
//        }
//        printf("%d\n");
        if(level[t]<0) return flow;
        int f;
        memcpy(cnt, head, sizeof(head));
        while(true){
            if((f = dfs(s, t, INF))<=0){
                break;
            }
            //else printf("%d\n", f);
            flow += f;
            //printf("test123:%d,%d\n", flow, f);
        }
    }
    return flow;
}
struct  Node{
    int in[max_in], out[max_in];
    int in_number, out_number;
    Node(){
        this->in_number = 0;
        this->out_number = 0;
    }
}node[maxn>>1];
int main()
{
    while(~scanf("%d%d", &P, &N)){
        e = 0;
        s = 0, t = 2*N+1;
        memset(head, -1, sizeof(head));
        for(int i=1; i<=N; i++){
            int wei;
            scanf("%d", &wei);
            add_edge(i, i+N, wei);
            for(int j=0; j<P; j++){
                scanf("%d", &node[i].in[j]);
                //不是2吗
                if(node[i].in[j] == 1)node[i].in_number++;
            }
            for(int j=0; j<P; j++){
                scanf("%d", &node[i].out[j]);
                if(node[i].out[j] == 0) node[i].out_number++;
            }
            if(node[i].in_number == 0) add_edge(s, i, INF);
            if(node[i].out_number == 0) add_edge(i+N, t, INF);
            for(int j=1; j<i; j++){
                if(node[j].out_number!=0&&node[i].in_number!=0){
                    bool flag = true;
                    for(int k=0; k<P&&flag; k++){
                        if(node[j].out[k]+node[i].in[k] == 1){
                            flag = false;
                        }
                    }
                    if(flag){
                        add_edge(j+N, i, INF);
                    }
                }
            }
            for(int j=1; j<i; j++){
                if(node[j].in_number!=0&&node[i].out_number!=0){
                    bool flag = true;
                    for(int k=0; k<P&&flag; k++){
                        if(node[j].in[k]+node[i].out[k] == 1){
                            flag = false;
                        }
                    }
                    if(flag){
                        add_edge(i+N, j, INF);
                    }
                }
            }
        }
//        for(int i=0; i<=2*N+1; i++){
//            for(int j=head[i]; j!=-1; j=nex[j]){
//                printf("node%d-->%d: %d\n",i, to[j], j);
//            }
//            printf("\n");
//        }
        printf("%d ", max_flow(s, t));
        int tot=0;
        for(int i=0; i<e; i++){
            if(flow[i]<=0||from[i] == s || to[i] == t || to[i] - from[i]==N){
                continue;
            }
            from[tot] = from[i]-N>0?from[i]-N:from[i];
            to[tot] = to[i]-N>0?to[i]-N:to[i];
            flow[tot] = flow[i];
            tot++;
        }
        printf("%d\n", tot);
        for(int i=0; i<tot; i++){
            printf("%d %d %d\n", from[i], to[i], flow[i]);
        }
    }
    return 0;
}

统计最小割的边数

Q：最小割可能有多种方案，那么该怎么统计最小割的边数呢？
A：建边的时候每边权\(W = W*(E+1)+1\), 得到的最大流为\(\frac{maxflow}{E+1}\)(取整), 最小割的边为\(maxflow\%(E+1)\).

未解决的问题

本文标题:网络流二十四题

文章作者:Babydragon

发布时间:2017-10-09, 23:37:43

最后更新:2018-05-22, 19:58:56

原始链接:http://baolintian.github.io/2017/10/09/网络流二十四题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 最大流模板
  2. 2. 题目链接
  3. 3. 题解
  4. 4. AC代码
  5. 5. 最小费流模板题
  6. 6. 题意
  7. 7. 题解
  8. 8. AC代码
  9. 9. 最大流
    1. 9.1. 题意
    2. 9.2. 题解
    3. 9.3. 代码
  10. 10. 统计最小割的边数
  11. 11. 未解决的问题
{{ live2d() }}