• <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>
            

    
            

            




            







												


        


            


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





            
	    
    




            






            

				

            

            

	

            My Links
            

	

            Blog Stats
            
	
	
	

            常用鏈接
            


            留言簿
            


		
            隨筆分類
            
		
				
			
	
		
            隨筆檔案
            
		
				
			
	
		
            文章分類
            
		
				
			
	
		
            ACMER
            
		
				
			
	


            搜索
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            




            


    
    







            
	   
	



天堂久久天堂AV色综合|
亚洲AV无一区二区三区久久|
91精品国产高清久久久久久91|
久久精品国产99国产电影网
|
久久精品国产久精国产一老狼|
无码精品久久久天天影视|
久久99国产精品久久99|
日产久久强奸免费的看|
浪潮AV色综合久久天堂|
国产精品九九久久精品女同亚洲欧美日韩综合区|
成人精品一区二区久久|
日韩精品久久无码中文字幕|
国产成人久久久精品二区三区|
欧洲精品久久久av无码电影|
久久亚洲色一区二区三区|
久久夜色tv网站|
国产91色综合久久免费|
免费精品久久天干天干|
国产高清国内精品福利99久久|
欧美精品国产综合久久|
欧美久久综合九色综合|
久久精品国产色蜜蜜麻豆|
2021少妇久久久久久久久久|
中文字幕热久久久久久久|
色婷婷综合久久久久中文字幕|
热久久这里只有精品|
7777久久亚洲中文字幕|
久久国产欧美日韩精品|
亚洲精品乱码久久久久久自慰|
欧美亚洲国产精品久久久久|
久久亚洲精品无码观看不卡|
久久99精品九九九久久婷婷|
久久97久久97精品免视看|
国产福利电影一区二区三区久久老子无码午夜伦不
|
热99re久久国超精品首页|
国产Av激情久久无码天堂|
久久99精品国产自在现线小黄鸭|
伊人久久无码中文字幕|
日韩乱码人妻无码中文字幕久久|
国内精品伊人久久久久av一坑|
久久精品国产亚洲一区二区|