POJ 1459 Power Network（ISAP）

Posted on | In | 阅读

ISAP算法模板

最大流增广路算法大致有三个优化等级

  1. EK算法（Edmonds Karp）通过dfs每次在残量网络中找到一条可行的增广路进行增广
  2. Dinic算法 在每次dfs寻找增广路前，先进行一次dfs标号，流量只沿着源点到汇点之间的最短路进行增广，这就相当于给了流一个势能，水只会向下流而不会随处流动，大大所短了EK算法中发现的增广路，提高了效率
  3. ISAP算法，在Dinic算法的基础上进一步优化，并不需要在每次增广前都用bfs重新标号，而是只进行一次标号，之后在一个结点无法增广时才考虑修改节点的标号，同时加入一个gap优化，当某一个标号的节点个数为0时，停止增广，输出最大流。

C++ Code

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#define MAX_NODE 105
#define INF 150000

using namespace std;

struct Edge{
    int from;
    int to;
    int cap;
    int flow;
    Edge(int f, int t, int c, int fw){
        from = f;
        to = t;
        cap = c;
        flow = fw;
    }
};

vector<Edge> edges;
vector<int> mp[MAX_NODE], prefix[MAX_NODE]; //the suffix edges of every node, the prefix nodes of every node
int deep[MAX_NODE], num[MAX_NODE], cur[MAX_NODE], pre[MAX_NODE];
int n, np, nc, m;

void add(int from, int to, int cap){
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    int sz = edges.size();
    mp[from].push_back(sz-2);
    mp[to].push_back(sz-1);
}

void bfs(int s, int t){
    memset(deep, -1, sizeof(deep));
    queue<int> q;
    q.push(s);
    deep[s] = 0;
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int i = 0; i < prefix[cur].size(); i++){
            int to = prefix[cur][i];
            if(deep[to] < 0){
                deep[to] = deep[cur] + 1;
                q.push(to);
            }
        }
    }
}

int augument(int s, int t){
    int pos = t;
    int flow = INF;
    while(pos != s){
        Edge &e = edges[pre[pos]];
        flow = min(flow, e.cap - e.flow);
//        printf("flow %d\n", flow);
//        printf("%d %d\n", e.cap, e.flow);
        pos = e.from;
    }
    pos = t;
    while(pos != s){
        edges[pre[pos]].flow += flow;
        edges[pre[pos]^1].flow -= flow;
        pos = edges[pre[pos]].from;
    }
    return flow;
}

int ISAP(int s, int t){
    int flow = 0;
    bool flag = false;
    bfs(t, s);
    memset(cur, 0, sizeof(cur));
    memset(num, 0, sizeof(num));
    for(int i = 0; i < n; i++){
        num[deep[i]]++;
    }
    int pos = s;
    while(deep[s] < n){
        if(pos == t){
            //augument one path successfully
            flow += augument(s, t);
            //continue the next one
            pos = s;
        }
        flag = false;
        for(int i = cur[pos]; i < mp[pos].size(); i++){
            Edge &e = edges[mp[pos][i]];
            if(e.cap > e.flow && deep[pos] == deep[e.to] + 1){
                flag = true;
                cur[pos] = i;
                pre[e.to] = mp[pos][i];
                pos = e.to;
                break;
            }
        }
        if(flag == false){
            int mi = n-1;
            for(int i = 0; i < mp[pos].size(); i++){
                Edge &e = edges[mp[pos][i]];
                if(e.cap > e.flow){
                    mi = min(mi, deep[e.to]);
                }
            }
            //gap
            num[deep[pos]]--;
            if(num[deep[pos]] == 0)
                break;
            num[mi+1]++;
            deep[pos] = mi+1;
            cur[pos] = 0;
            if(pos != s)
                pos = edges[pre[pos]].from;
        }
    }
    return flow;
}


int main(){
    while(~scanf("%d%d%d%d", &n, &np, &nc, &m)){
        n += 2;
        for(int i = 0; i < n; i++){
            mp[i].clear();
            prefix[i].clear();
        }
        edges.clear();
        int from, to, cap;
        for(int i = 0; i < m; i++){
            scanf(" (%d,%d)%d", &from, &to, &cap);
            add(from, to, cap);
            prefix[to].push_back(from);
        }
        for(int i = 0; i < np; i++){
            scanf(" (%d)%d", &from, &cap);
            add(n-2, from, cap);
            prefix[from].push_back(n-2);
        }
        for(int i = 0; i < nc; i++){
            scanf(" (%d)%d", &from, &cap);
            add(from, n-1, cap);
            prefix[n-1].push_back(from);
        }
        int ans = ISAP(n-2, n-1);
        printf("%d\n", ans);
    }
    return 0;
}