In The End

个人博客

0%

POJ1273题：EK算法与Dinic算法求最大流

发表于 更新于 分类于 ，

题目

题目传送门：http://poj.org/problem?id=1273

Drainage Ditches

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 88479 Accepted: 34326

Description

Every time it rains on Farmer John’s fields, a pond forms over Bessie’s favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie’s clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.

Input

The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.

Output

For each case, output a single integer, the maximum rate at which water may emptied from the pond.

Sample Input

1
2
3
4
5
6
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

Sample Output

1
50

题解

一道EK算法求最大流的裸题

EK算法是根据FF算法发展演变过来的一种求最大流最小割的网络流算法，核心就是根据bfs或dfs(其实一般都是bfs啦)找到增广路，然后对增广路流过值的残余做反向边的一个比较简单暴力的算法，写起来也比较容易，这里就不做多解释了，网上的博客也很多的

这里放出我的EK算法的代码

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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=210;

queue<int> que;
int n,m,mp[maxn][maxn],pre[maxn];

int bfs(int s,int t){
    int vis[maxn],flow[maxn];
    memset(vis,0,sizeof(vis));
    memset(flow,-1,sizeof(flow));
    while(!que.empty()) que.pop();
    pre[s]=s,vis[s]=1,flow[s]=1<<30,que.push(s);
    while(!que.empty()){
        int u=que.front();que.pop();
        for(int i=1;i<=n;i++){
            if(!vis[i]&&mp[u][i]){
                flow[i]=min(flow[u],mp[u][i]);
                vis[i]=1;
                pre[i]=u;
                que.push(i);
            }
        }
    }
    if(flow[t]==-1)
        return 0;
    return flow[t];
}

int EK(int s,int t){
    int flow,ans=0;
    while(flow=bfs(s,t)){
        ans+=flow;
        int x=t;
        while(x!=s){
            mp[pre[x]][x]-=flow;
            mp[x][pre[x]]+=flow;
            x=pre[x];
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    int si,ei,ci;
    while(cin>>m>>n){
        memset(mp,0,sizeof(mp));
        for(int i=0;i<m;i++)
            cin>>si>>ei>>ci,mp[si][ei]+=ci;
        int s=1,t=n;
        cout << EK(s,t) << endl;
    }
    return 0;
}

更新Dinic算法，Dinic算法也是在EK算法的基础上做改进，利用BFS将网络进行分层，然后使用DFS直接多路增广提高效率

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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=210;
const int inf=1<<30;

struct edge{
    int v,f,nxt;
}e[maxn<<1];

int num,n,m,s,t,g[maxn];
queue<int> que;
int vis[maxn],d[maxn];

void addedge(int u,int v,int val){
    e[++num].v=v;
    e[num].f=val;
    e[num].nxt=g[u];
    g[u]=num;
    e[++num].v=u;
    e[num].f=0;
    e[num].nxt=g[v];
    g[v]=num;
}

void bfs(){
    memset(d,0,sizeof(d));
    while(!que.empty()) que.pop();
    vis[s]=1,que.push(s);
    while(!que.empty()){
        int u=que.front();que.pop();
        for(int i=g[u];i;i=e[i].nxt){
            if(e[i].f&&!vis[e[i].v]){
                d[e[i].v]=d[u]+1;
                vis[e[i].v]=1;
                que.push(e[i].v);
            }
        }
    }
}

int dfs(int u,int flow){
    if(u==t)
        return flow;
    else{
        int ans=0;
        for(int i=g[u];flow&&i;i=e[i].nxt){
            if(e[i].f&&d[e[i].v]==d[u]+1){
                int dd=dfs(e[i].v,min(e[i].f,flow));
                e[i].f-=dd;
                e[i^1].f+=dd;
                flow-=dd;
                ans+=dd;
            }
        }
        return ans;
    }
}

int dinic(){
    int ans=0;
    while(true){
        memset(vis,0,sizeof(vis));
        bfs();
        if(!vis[t])
            return ans;
        ans+=dfs(s,inf);
    }
}

int main(){
    ios::sync_with_stdio(false);
    while(cin>>m>>n){
        memset(g,0,sizeof(g));
        num=1;
        int x,y,z;
        while(m--){
            cin>>x>>y>>z;
            addedge(x,y,z);
        }
        s=1,t=n;
        cout << dinic() << endl;
    }
    return 0;
}