青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(468) 評論(0)  編輯 收藏 引用 所屬分類: NetWork Flow


只有注冊用戶登錄后才能發表評論。
網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


My Links

Blog Stats

常用鏈接

留言簿

隨筆分類

隨筆檔案

文章分類

ACMER

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            
国产日韩欧美一区二区|
韩日在线一区|
国产精品久久中文|
国产精品国产三级国产普通话99|
欧美日韩三级视频|
欧美视频免费在线|
欧美视频一区二区在线观看|
欧美日韩亚洲另类|
欧美新色视频|
国产精品日日做人人爱|
国产日韩在线看片|
精品av久久707|
亚洲欧洲一级|
一区二区三区精品国产|
亚洲午夜影视影院在线观看|
亚洲欧美激情精品一区二区|
欧美一区亚洲二区|
免费观看在线综合色|
欧美激情二区三区|
亚洲狼人精品一区二区三区|
99国产精品|
午夜精品久久|
免费看成人av|
欧美精品xxxxbbbb|
国产精品一区二区在线观看网站
|
午夜在线一区|
久久久亚洲人|
欧美美女日韩|
国产日产亚洲精品|
亚洲国产小视频在线观看|
一区二区三区久久久|
欧美一二三视频|
欧美成人第一页|
av不卡在线看|
欧美一区精品|
欧美成人免费小视频|
国产精品不卡在线|
精品福利免费观看|
亚洲午夜精品在线|
开心色5月久久精品|
日韩天堂av|
久久精品30|
欧美色精品在线视频|
影音先锋中文字幕一区二区|
亚洲天堂第二页|
麻豆久久精品|
亚洲视频每日更新|
免费成人你懂的|
国产精品丝袜91|
亚洲日本aⅴ片在线观看香蕉|
亚洲欧美久久久|
亚洲国产裸拍裸体视频在线观看乱了中文|
夜夜躁日日躁狠狠久久88av|
久久福利影视|
国产精品v亚洲精品v日韩精品|
一区二区三区自拍|
先锋影院在线亚洲|
亚洲精品国产精品乱码不99|
欧美在线视频免费|
国产精品wwwwww|
亚洲精品字幕|
久久综合一区二区|
亚洲女同精品视频|
欧美日韩国产首页|
亚洲第一黄网|
久久国产精品久久w女人spa|
亚洲麻豆一区|
美女尤物久久精品|
国模叶桐国产精品一区|
亚洲一区日本|
亚洲日本va午夜在线影院|
久久久999精品视频|
国产伦精品一区二区三区照片91|
日韩视频在线一区二区三区|
猛男gaygay欧美视频|
亚洲欧美日韩精品久久亚洲区|
欧美日韩的一区二区|
亚洲人成小说网站色在线|
久久久噜噜噜久噜久久|
亚洲欧美日韩区|
国产精品久久久对白|
一卡二卡3卡四卡高清精品视频|
欧美韩日一区|
久久综合一区二区|
伊人成人网在线看|
久久婷婷蜜乳一本欲蜜臀|
午夜精品成人在线视频|
国产精品久久久久一区|
中文在线资源观看视频网站免费不卡|
亚洲第一精品影视|
美女尤物久久精品|
亚洲日本在线观看|
欧美激情第六页|
欧美va天堂|
亚洲精品资源|
亚洲日韩中文字幕在线播放|
欧美精品三区|
亚洲一区二区成人|
在线一区二区三区做爰视频网站|
欧美精品自拍|
日韩一级欧洲|
99国产精品久久久久久久成人热|
欧美日韩国产精品专区|
亚洲天堂av在线免费观看|
日韩视频不卡中文|
国产精品av免费在线观看|
午夜日韩在线|
欧美在线观看一区|
在线看一区二区|
亚洲成人在线网|
欧美美女视频|
亚洲欧美日韩区|
亚欧成人在线|
在线观看欧美黄色|
亚洲激情视频网站|
欧美日韩一区二区三区在线看
|
黄色成人91|
久久久久九九视频|
美女福利精品视频|
一本综合久久|
亚洲欧美中文在线视频|
国产一区99|
亚洲国产福利在线|
国产精品99免视看9|
久久久999精品免费|
久久免费偷拍视频|
日韩一级网站|
亚洲永久网站|
国产亚洲欧美一区在线观看|
久久亚洲综合色一区二区三区|
男同欧美伦乱|
亚洲综合社区|
久久精品人人做人人爽|
亚洲精品一二区|
亚洲专区在线|
在线观看日韩一区|
日韩一二三区视频|
国产美女一区二区|
欧美国产精品v|
国产精品进线69影院|
美女999久久久精品视频|
欧美日韩精品三区|
欧美日韩专区在线|
久久久青草青青国产亚洲免观|
模特精品裸拍一区|
欧美在线看片a免费观看|
免费国产一区二区|
欧美一区二区三区四区在线观看地址
|
欧美韩日一区|
久久成人av少妇免费|
欧美成人免费观看|
久久久久国产精品厨房|
欧美日韩国产123|
免费高清在线一区|
国产精品区一区|
亚洲电影免费观看高清完整版在线|
国产精品日韩专区|
亚洲精品欧美精品|
伊人久久婷婷|
亚洲欧美视频一区|
一区二区欧美在线观看|
久久午夜精品一区二区|
欧美一区二区久久久|
欧美激情视频一区二区三区免费|
久久九九热免费视频|
欧美日韩亚洲国产精品|
欧美激情小视频|
国产在线播精品第三|
亚洲线精品一区二区三区八戒|
亚洲日本va午夜在线电影|
欧美一区二区性|
亚洲欧美另类久久久精品2019|
欧美激情视频网站|
欧美成人有码|
永久免费精品影视网站|
亚洲欧美日韩在线观看a三区|
国产精品99久久不卡二区|
麻豆成人精品|
久热精品视频在线|
国产毛片一区|
亚洲性夜色噜噜噜7777|
中文亚洲欧美|
欧美日韩免费观看一区=区三区|
欧美成人综合一区|
影音欧美亚洲|
久久久精彩视频|
久久久精品国产免大香伊|
国产精品视频免费一区|
日韩午夜剧场|
一区二区国产日产|
欧美高清视频一二三区|
欧美国产精品劲爆|
最新日韩精品|
美日韩精品视频免费看|
欧美成人免费在线观看|
在线看国产日韩|
久久综合色综合88|
欧美va亚洲va香蕉在线|
伊人成人开心激情综合网|
久久亚洲私人国产精品va媚药|