• <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>
            posts - 7,comments - 3,trackbacks - 0
            Minimum Cut
            Time Limit: 10000MSMemory Limit: 65536K
            Total Submissions: 5403Accepted: 2113
            Case Time Limit: 5000MS

            Description

            Given an undirected graph, in which two vertices can be connected by multiple edges, what is the size of the minimum cut of the graph? i.e. how many edges must be removed at least to disconnect the graph into two subgraphs?

            Input

            Input contains multiple test cases. Each test case starts with two integers N and M (2 ≤ N ≤ 500, 0 ≤ M ≤ N × (N − 1) ⁄ 2) in one line, where N is the number of vertices. Following are M lines, each line contains M integers AB and C (0 ≤ AB < NA ≠ BC > 0), meaning that there C edges connecting vertices A and B.

            Output

            There is only one line for each test case, which contains the size of the minimum cut of the graph. If the graph is disconnected, print 0.

            Sample Input

            3 3
            0 1 1
            1 2 1
            2 0 1
            4 3
            0 1 1
            1 2 1
            2 3 1
            8 14
            0 1 1
            0 2 1
            0 3 1
            1 2 1
            1 3 1
            2 3 1
            4 5 1
            4 6 1
            4 7 1
            5 6 1
            5 7 1
            6 7 1
            4 0 1
            7 3 1

            Sample Output

            2
            1
            2

            Source

            Baidu Star 2006 Semifinal 
            Wang, Ying (Originator) 
            Chen, Shixi (Test cases)

            全局最小割,模板題,Stor-Wagner算法,大概就是prime的最大生成樹,具體的網上有很多,可以google到的,不多說了。
            代碼:
            #include<stdio.h>
            #include<string.h>

            #define NN 504
            #define INF 1 << 30
            int vis[NN];
            int wet[NN];
            int combine[NN];
            int map[NN][NN];

            int S, T, minCut, N;
            void Search()
            {
                
            int i, j, Max, tmp;
                memset(vis, 
            0sizeof(vis));
                memset(wet, 
            0sizeof(wet));
                S 
            = T = -1;
                
            for (i = 0; i < N; i++)
                {
                    Max 
            = -INF;
                    
            for (j = 0; j < N; j++)
                    {
                        
            if (!combine[j] && !vis[j] && wet[j] > Max)
                        {
                            tmp 
            = j;
                            Max 
            = wet[j];
                        }
                    }
                    
            if (T == tmp) return;
                    S 
            = T;
                    T 
            = tmp;
                    minCut 
            = Max;
                    vis[tmp] 
            = 1;
                    
            for (j = 0; j < N; j++)
                    {
                        
            if (!combine[j] && !vis[j])
                        {
                            wet[j] 
            += map[tmp][j];
                        }
                    }
                }
            }
            int Stoer_Wagner()
            {
                
            int i, j;
                memset(combine, 
            0sizeof(combine));
                
            int ans = INF;
                
            for (i = 0; i < N - 1; i++)
                {
                    Search();
                    
            if (minCut < ans) ans = minCut;
                    
            if (ans == 0return 0;
                    combine[T] 
            = 1;
                    
            for (j = 0; j < N; j++)
                    {
                        
            if (!combine[j])
                        {
                            map[S][j] 
            += map[T][j];
                            map[j][S] 
            += map[j][T];
                        }
                    }
                }
                
            return ans;
            }
            int main()
            {
                
            int a, b, c, M;
                
            while(scanf("%d%d"&N, &M) != EOF)
                {
                    memset(map, 
            0sizeof(map));
                    
            while(M--)
                    {
                        scanf(
            "%d%d%d"&a, &b, &c);
                        map[a][b] 
            += c;
                        map[b][a] 
            += c;
                    }
                    printf(
            "%d\n", Stoer_Wagner());
                }
                
            return 0;
            }
            posted on 2011-10-15 22:10 LLawliet 閱讀(214) 評論(0)  編輯 收藏 引用 所屬分類: 網絡流
            99国内精品久久久久久久| 久久综合视频网| 精品乱码久久久久久夜夜嗨| 精品久久久久中文字| 欧美激情一区二区久久久| 久久亚洲国产成人精品性色| 国产亚洲欧美成人久久片| 久久嫩草影院免费看夜色| 亚洲午夜无码久久久久| 久久久久久a亚洲欧洲aⅴ| 亚洲&#228;v永久无码精品天堂久久 | 久久久久久久综合日本| 久久综合久久美利坚合众国| 国产欧美久久一区二区| 久久亚洲AV成人无码| 国产精品日韩深夜福利久久| 亚洲国产另类久久久精品| 蜜桃麻豆www久久国产精品| 久久综合久久综合久久| 天天躁日日躁狠狠久久| 色99久久久久高潮综合影院| 国产欧美一区二区久久| 精品久久久久久亚洲精品| 中文字幕精品久久久久人妻| 99精品伊人久久久大香线蕉| 色综合久久无码中文字幕| 久久精品极品盛宴观看| 欧美久久久久久午夜精品| 99久久精品九九亚洲精品| 久久久精品2019免费观看| 久久精品日日躁夜夜躁欧美| 午夜精品久久久久久影视777| 亚洲国产精品久久久久婷婷软件 | 亚洲AV日韩精品久久久久久 | 久久久久久毛片免费播放| 热99RE久久精品这里都是精品免费| 精品久久久久久99人妻| 久久久久亚洲AV无码去区首| 久久国产成人| 亚洲人AV永久一区二区三区久久| 久久精品国产亚洲一区二区三区|