icecream

我的代码备份！

Maximum Flow Algorithms

 

 1#include <iostream>
 2#include <cstring>
 3using namespace std;
 4
 5const int MAX = 128;
 6class Network
 7{
 8public:
 9    int r[MAX][MAX], u[MAX][MAX], lnk[MAX][MAX];
10    int pre[MAX], s, t, size;
11
12    bool build();
13    int augment();
14    int MaxFlow();
15};
16
17bool Network::build()
18{
19    int n, n1, n2, m;
20    if (scanf("%d %d %d %d", &n, &n1, &n2, &m) < 4) return false;
21    s = n, t = n + 1, size = n + 2;
22    memset(u, 0, sizeof(u)), memset(r, 0, sizeof(r));
23    
24    int from, to, d, v, z;
25    for (int i = 0; i < m; ++i)
26        scanf("\n(%d,%d)%d", &from, &to, &d), r[from][to] = u[from][to] = d;
27    for (int i = 0; i < n1; ++i)
28        scanf("\n(%d)%d", &v, &z), r[s][v] = u[s][v] = z;
29    for (int i = 0; i < n2; ++i)
30        scanf("\n(%d)%d", &v, &z), r[v][t] = u[v][t] = z;
31
32    for (int i = 0; i < size; ++i) lnk[i][0] = 0;
33    for (int i = 0; i < size; ++i)
34        for (int j = i+1; j < size; ++j)
35            if (u[i][j] || u[j][i]) lnk[i][++lnk[i][0]] = j, lnk[j][++lnk[j][0]] = i;
36    return true;
37}
38
39int Network::augment()
40{
41    int q[MAX], head = 0, tail = 0, flow[MAX] = {0};
42    memset(pre, -1, sizeof(pre));
43
44    q[tail++] = s, pre[s] = s, flow[s] = (1 << 28);
45    while (head < tail)
46    {
47        int top = q[head++];
48        for (int i = 1; i <= lnk[top][0]; ++i)
49        {
50            if (r[top][lnk[top][i]] <= 0 || pre[lnk[top][i]] != -1) continue;
51            pre[lnk[top][i]] = top, flow[lnk[top][i]] = min(flow[top], r[top][lnk[top][i]]);
52            q[tail++] = lnk[top][i];
53            if (lnk[top][i] == t) return flow[t];
54        }
55    }
56    return 0;
57}
58
59int Network::MaxFlow()
60{
61    int mxFlow = 0, cnt = 0;
62    while (cnt = augment())
63    {
64        for (int p = t; p != s; p = pre[p])
65            r[pre[p]][p] -= cnt, r[p][pre[p]] += cnt;
66        mxFlow += cnt;
67    }
68    return mxFlow;
69}
70
71int main()
72{
73    Network network;
74    while (network.build()) printf( "%d\n", network.MaxFlow() );
75    return 0;
76}
77

  1//Shortest Augmenting Path O(n^2*m)
  2#include <iostream>
  3#include <cstring>
  4using namespace std;
  5
  6const int MAX = 128;
  7class Network
  8{
  9public:
 10    int r[MAX][MAX], u[MAX][MAX], lnk[MAX][MAX];
 11    int h[MAX], cnt[MAX], currArc[MAX];
 12    int pre[MAX], s, t, size;
 13
 14    bool build();
 15    void get_distance_label();
 16    int MaxFlow();
 17};
 18
 19bool Network::build()
 20{
 21    int n, n1, n2, m;
 22    if (scanf("%d %d %d %d", &n, &n1, &n2, &m) < 4) return false;
 23    s = n, t = n + 1, size = n + 2;
 24    memset(u, 0, sizeof(u)), memset(r, 0, sizeof(r));
 25    
 26    int from, to, d, v, z;
 27    for (int i = 0; i < m; ++i)
 28        scanf("\n(%d,%d)%d", &from, &to, &d), r[from][to] = u[from][to] = d;
 29    for (int i = 0; i < n1; ++i)
 30        scanf("\n(%d)%d", &v, &z), r[s][v] = u[s][v] = z;
 31    for (int i = 0; i < n2; ++i)
 32        scanf("\n(%d)%d", &v, &z), r[v][t] = u[v][t] = z;
 33
 34    for (int i = 0; i < size; ++i) lnk[i][0] = 0, currArc[i] = 1;
 35    for (int i = 0; i < size; ++i)
 36        for (int j = i+1; j < size; ++j)
 37            if (u[i][j] || u[j][i]) lnk[i][++lnk[i][0]] = j, lnk[j][++lnk[j][0]] = i;
 38    return true;
 39}
 40
 41void Network::get_distance_label()
 42{
 43    int q[MAX], head = 0, tail = 0;
 44    q[tail++] = t, h[t] = 0, ++ cnt[h[t]];
 45    while (head < tail)
 46    {
 47        int top = q[head++];
 48        for (int i = 1; i <= lnk[top][0]; ++i)
 49        {
 50            if (r[lnk[top][i]][top] <= 0 || h[lnk[top][i]] < size) continue;
 51            q[tail++] = lnk[top][i];
 52            h[lnk[top][i]] = h[top] + 1, ++ cnt[h[lnk[top][i]]];
 53        }
 54    }
 55}
 56
 57int Network::MaxFlow()
 58{
 59    memset(h, 1, sizeof(h)), memset(cnt, 0, sizeof(cnt));
 60    get_distance_label();
 61
 62    int nowP = s, mxFlow = 0, pre[MAX] = { 0 };
 63    while (h[s] < size)
 64    {
 65        for (;currArc[nowP] <= lnk[nowP][0]; ++currArc[nowP])
 66        {
 67            int temp = lnk[nowP][currArc[nowP]];
 68            if (h[temp] + 1 != h[nowP] || r[nowP][temp] <= 0) continue;
 69            break;
 70        }
 71        if (currArc[nowP] == lnk[nowP][0]+1)
 72        {
 73            if (--cnt[h[nowP]] == 0) return mxFlow;
 74            h[nowP] = MAX << 1;
 75            for (int i = 1; i <= lnk[nowP][0]; ++i)
 76                if (r[nowP][lnk[nowP][i]]) 
 77                    h[nowP] = min(h[nowP], h[lnk[nowP][i]]+1);
 78            ++cnt[h[nowP]];
 79            currArc[nowP] = 1;
 80            if (nowP != s) nowP = pre[nowP];
 81            continue;
 82        }
 83        pre[lnk[nowP][currArc[nowP]]] = nowP, nowP = lnk[nowP][currArc[nowP]];
 84        if (nowP == t)
 85        {
 86            int mxAddFlow = (1 << 28);
 87            for (int temp = t; temp != s; temp = pre[temp])
 88                mxAddFlow = min(mxAddFlow, r[pre[temp]][temp]);
 89            for (int temp = t; temp != s; temp = pre[temp])
 90                r[pre[temp]][temp] -= mxAddFlow, r[temp][pre[temp]] += mxAddFlow;
 91            mxFlow += mxAddFlow;
 92            nowP = s;
 93        }
 94    }
 95    return mxFlow;
 96}
 97
 98int main()
 99{
100    Network network;
101    while (network.build()) printf( "%d\n", network.MaxFlow() );
102    return 0;
103}
104
105

  1//Dinic O(n^2*m)
  2#include <iostream>
  3#include <cstring>
  4using namespace std;
  5
  6const int MAX = 128;
  7class Network
  8{
  9public:
 10    int r[MAX][MAX], u[MAX][MAX], lnk[MAX][MAX];
 11    int h[MAX], cnt[MAX], currArc[MAX];
 12    int pre[MAX], s, t, size;
 13    bool blocked[MAX];
 14
 15    bool build();
 16    int get_distance_label();
 17    int MaxFlow();
 18};
 19
 20bool Network::build()
 21{
 22    int n, n1, n2, m;
 23    if (scanf("%d %d %d %d", &n, &n1, &n2, &m) < 4) return false;
 24    s = n, t = n + 1, size = n + 2;
 25    memset(u, 0, sizeof(u)), memset(r, 0, sizeof(r));
 26    
 27    int from, to, d, v, z;
 28    for (int i = 0; i < m; ++i)
 29        scanf("\n(%d,%d)%d", &from, &to, &d), r[from][to] = u[from][to] = d;
 30    for (int i = 0; i < n1; ++i)
 31        scanf("\n(%d)%d", &v, &z), r[s][v] = u[s][v] = z;
 32    for (int i = 0; i < n2; ++i)
 33        scanf("\n(%d)%d", &v, &z), r[v][t] = u[v][t] = z;
 34
 35    for (int i = 0; i < size; ++i) lnk[i][0] = 0, currArc[i] = 1;
 36    for (int i = 0; i < size; ++i)
 37        for (int j = i+1; j < size; ++j)
 38            if (u[i][j] || u[j][i]) lnk[i][++lnk[i][0]] = j, lnk[j][++lnk[j][0]] = i;
 39    return true;
 40}
 41
 42int Network::get_distance_label()
 43{
 44    memset(h, 1, sizeof(h));
 45    int q[MAX], head = 0, tail = 0;
 46    q[tail++] = t, h[t] = 0, ++ cnt[h[t]];
 47    while (head < tail)
 48    {
 49        int top = q[head++];
 50        for (int i = 1; i <= lnk[top][0]; ++i)
 51        {
 52            if (r[lnk[top][i]][top] <= 0 || h[lnk[top][i]] < size) continue;
 53            q[tail++] = lnk[top][i];
 54            h[lnk[top][i]] = h[top] + 1, ++ cnt[h[lnk[top][i]]];
 55        }
 56    }
 57    return h[s];
 58}
 59
 60int Network::MaxFlow()
 61{
 62    int mxFlow = 0;
 63    while (get_distance_label() < size)
 64    {
 65        memset(blocked, false, sizeof(blocked));
 66        memset(currArc, 0, sizeof(currArc));
 67        int nowP = s;
 68        while (!blocked[s])
 69        {
 70            if (blocked[nowP]) nowP = pre[nowP];
 71            for (; currArc[nowP] <= lnk[nowP][0]; ++currArc[nowP])
 72            {
 73                int temp = lnk[nowP][currArc[nowP]];
 74                if (r[nowP][temp] <= 0 || h[temp]+1 != h[nowP] || blocked[temp])
 75                    continue;
 76                break;
 77            }
 78            if (currArc[nowP] == lnk[nowP][0] + 1)
 79            {
 80                blocked[nowP] = true;
 81                if (nowP != s) nowP = pre[nowP];
 82                continue;
 83            }
 84            pre[lnk[nowP][currArc[nowP]]] = nowP, nowP = lnk[nowP][currArc[nowP]];
 85            if (nowP == t)
 86            {
 87                int k = t, mxAddFlow = (1 << 28);
 88                for (int temp = t; temp != s; temp = pre[temp])
 89                    if (r[pre[temp]][temp] < mxAddFlow)
 90                        k = pre[temp], mxAddFlow = r[pre[temp]][temp];
 91                for (int temp = t; temp != s; temp = pre[temp])
 92                    r[pre[temp]][temp] -= mxAddFlow, r[temp][pre[temp]] += mxAddFlow;
 93                mxFlow += mxAddFlow, nowP = k;
 94            }
 95        }
 96    }
 97    return mxFlow;
 98}
 99
100int main()
101{
102    Network network;
103    while (network.build()) printf( "%d\n", network.MaxFlow() );
104    return 0;
105}
106
107

  1//Highest label preflow push O(n^2*sqrt(m))
  2#include <iostream>
  3#include <cstring>
  4using namespace std;
  5
  6const int MAX = 128;
  7class Node
  8{
  9public:
 10    int p, next;
 11    Node(int pp = 0, int nn = 0):
 12        p(pp), next(nn)
 13    {}
 14};
 15Node nodes[2*MAX*MAX];
 16
 17class Network
 18{
 19public:
 20    int r[MAX][MAX], u[MAX][MAX], lnk[MAX][MAX];
 21    int h[MAX], cnt[MAX], currArc[MAX], e[MAX], List[MAX];
 22    int pre[MAX], s, t, size, sn, level;
 23    
 24    void initial()
 25    {
 26        sn = level = 0;
 27        nodes[0] = Node(-1, 0);
 28    }
 29
 30    void insert(int L, int p)
 31    {
 32        nodes[++sn] = Node(p, List[L]), List[L] = sn;
 33    }
 34
 35    bool build();
 36    void get_distance_label();
 37    int MaxFlow();
 38};
 39
 40bool Network::build()
 41{
 42    int n, n1, n2, m;
 43    if (scanf("%d %d %d %d", &n, &n1, &n2, &m) < 4) return false;
 44    s = n, t = n + 1, size = n + 2;
 45    memset(u, 0, sizeof(u)), memset(r, 0, sizeof(r));
 46    
 47    int from, to, d, v, z;
 48    for (int i = 0; i < m; ++i)
 49        scanf("\n(%d,%d)%d", &from, &to, &d), r[from][to] = u[from][to] = d;
 50    for (int i = 0; i < n1; ++i)
 51        scanf("\n(%d)%d", &v, &z), r[s][v] = u[s][v] = z;
 52    for (int i = 0; i < n2; ++i)
 53        scanf("\n(%d)%d", &v, &z), r[v][t] = u[v][t] = z;
 54
 55    for (int i = 0; i < size; ++i) lnk[i][0] = 0, currArc[i] = 1;
 56    for (int i = 0; i < size; ++i)
 57        for (int j = i+1; j < size; ++j)
 58            if (u[i][j] || u[j][i]) lnk[i][++lnk[i][0]] = j, lnk[j][++lnk[j][0]] = i;
 59    return true;
 60}
 61
 62void Network::get_distance_label()
 63{
 64    memset(h, 1, sizeof(h)), memset(cnt, 0, sizeof(cnt));
 65    int q[MAX], head = 0, tail = 0;
 66    q[tail++] = t, h[t] = 0, ++ cnt[h[t]];
 67    while (head < tail)
 68    {
 69        int top = q[head++];
 70        for (int i = 1; i <= lnk[top][0]; ++i)
 71        {
 72            if (r[lnk[top][i]][top] <= 0 || h[lnk[top][i]] < size) continue;
 73            q[tail++] = lnk[top][i];
 74            h[lnk[top][i]] = h[top] + 1, ++ cnt[h[lnk[top][i]]];
 75        }
 76    }
 77}
 78
 79int Network::MaxFlow()
 80{
 81    initial();
 82    get_distance_label();
 83    
 84    if (h[s] > size) return 0;
 85    h[s] = size;
 86    memset(e, 0, sizeof(e)), memset(List, 0, sizeof(List));
 87    bool in[MAX] = { false };
 88    in[s] = true, in[t] = true;
 89    for (int i = 1; i <= lnk[s][0]; ++i)
 90    {
 91        if (r[s][lnk[s][i]])
 92        {
 93            if (in[lnk[s][i]] == false)
 94            {
 95                level = max(level, h[lnk[s][i]]);
 96                insert(h[lnk[s][i]], lnk[s][i]);
 97                in[lnk[s][i]] = true;
 98            }
 99            e[s] -= r[s][lnk[s][i]];
100            r[lnk[s][i]][s] = e[lnk[s][i]] = r[s][lnk[s][i]];
101            r[s][lnk[s][i]] = 0;
102        }
103    }
104
105    while (level)
106    {
107        for (; List[level]; List[level] = nodes[List[level]].next)
108        {
109            int now = nodes[List[level]].p;
110            for (; currArc[now] <= lnk[now][0]; ++currArc[now])
111            {
112                int temp = lnk[now][currArc[now]];
113                if (h[temp] + 1 == h[now] && r[now][temp])
114                {
115                    if (!in[temp]) insert(h[temp], temp);
116                    in[temp] = true;
117                    int flow_num = min(r[now][temp], e[now]);
118                    e[temp] += flow_num, e[now] -= flow_num;
119                    r[temp][now] += flow_num, r[now][temp] -= flow_num;
120                }
121            }
122            if (e[now])
123            {
124                if (--cnt[h[now]] == 0)
125                {
126                    for (int i = 0; i < size; ++i)
127                        if (h[i] > h[now] && h[i] <= size && i != s)
128                        {
129                            -- cnt[h[i]], h[i] = size + 1, ++ cnt[h[i]], currArc[i] = 1;
130                            if (in[i])level = max(level, h[i]+1);
131                        }
132                }
133                h[now] = 2*MAX;
134                for (int i = 1; i <= lnk[now][0]; ++i)
135                    if (r[now][lnk[now][i]]) h[now] = min(h[lnk[now][i]] + 1, h[now]);
136                level = max(level, h[now] + 1), ++ cnt[h[now]], currArc[now] = 1;
137                insert(h[now], now);
138                break;
139            }
140            else in[now] = false;
141        }
142        -- level;
143    }
144    return e[t];
145}
146
147int main()
148{
149    Network network;
150    while (network.build()) printf( "%d\n", network.MaxFlow() );
151    return 0;
152}
153

posted on 2010-05-05 14:15 icecream 阅读(503) 评论(0)  编辑 收藏 引用 所属分类: NetWork Flow


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


My Links

Blog Stats

常用链接

留言簿

随笔分类

随笔档案

文章分类

ACMER

搜索

最新评论

阅读排行榜

评论排行榜