Andrewei's Blog
0%

POJ1273(Drainage Ditches)

发表于 更新于 分类于 ，

题目链接：http://poj.org/problem?id=1273

题目大意:

下雨的时候约翰的田里总是积水，积水把他种的三叶草给淹了，他于是做了若干排水沟，每条沟在起始处安置一个阀门来控制这条沟的最大排水量，现在给出沟的条数以及阀门的个数。并给出每条沟的最大排水量。约翰的田里的积水处是阀门1，排出水的位置是最后一个阀门。求约翰在处理积水时的最大排出量。

思路:

题意抽象一下即有一个n个点的图, 边权代表最大流量, 求源点为1, 汇点为n的最大流.
题目为最大流的裸题, 用于练习算法模板.

参考代码

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
58
59
60
61
62
63
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 300;
const int MAX_INT = ((1 << 31) - 1);

int n, m;
int pre[MAXN];
bool vis[MAXN];
int mp[MAXN][MAXN];

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

int EK(int s, int t){
    int ans = 0;
    while(bfs(s, t)){
        int mi = MAX_INT;
        for(int i = t; i != s; i = pre[i]){
            mi = min(mi, mp[pre[i]][i]);
        }
        for(int i = t; i != s; i = pre[i]){
            mp[pre[i]][i] -= mi;
            mp[i][pre[i]] += mi;
        }
        ans += mi;
    }
    return ans;
}

int main(){
    while(scanf("%d%d", &m, &n) != EOF){
        int u, v, w;
        memset(mp, 0, sizeof(mp));
        for(int i = 0; i < m; i++){
            scanf("%d%d%d", &u, &v, &w);
            mp[u][v] += w;
        }
        printf("%d\n", EK(1, n));
    }
    return 0;
}

邻接表

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 <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 430;
const int MAX_INT = (1 << 30);

struct Edge{
    int v, nxt, w;
};

struct Node{
    int v, id;
};

int n, m, ecnt;
bool vis[MAXN];
int head[MAXN];
Node pre[MAXN];
Edge edge[MAXN];

void init(){
    ecnt = 0;
    memset(edge, 0, sizeof(edge));
    memset(head, -1, sizeof(head));
}

void addEdge(int u, int v, int w){
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].nxt = head[u];
    head[u] = ecnt++;
}

bool bfs(int s, int t){
    queue <int> que;
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    pre[s].v = s;
    vis[s] = true;
    que.push(s);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        for(int i = head[u]; i + 1; i = edge[i].nxt){
            int v = edge[i].v;
            if(!vis[v] && edge[i].w){
                pre[v].v = u;
                pre[v].id = i;
                vis[v] = true;
                if(v == t) return true;
                que.push(v);
            }
        }
    }
    return false;
}

int EK(int s, int t){
    int ans = 0;
    while(bfs(s, t)){
        int mi = MAX_INT;
        for(int i = t; i != s; i = pre[i].v){
            mi = min(mi, edge[pre[i].id].w);
        }
        for(int i = t; i != s; i = pre[i].v){
            edge[pre[i].id].w -= mi;
            edge[pre[i].id ^ 1].w += mi;
        }
        ans += mi;
    }
    return ans;
}

int main(){
    while(scanf("%d%d", &m, &n) != EOF){
        init();
        int u, v, w;
        for(int i = 0; i < m; i++){
            scanf("%d%d%d", &u, &v, &w);
            addEdge(u, v, w);
            addEdge(v, u, 0);
        }
        printf("%d\n", EK(1, n));
    }
    return 0;
}