• <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)  編輯 收藏 引用 所屬分類: 網絡流
            伊人久久国产免费观看视频| 天堂无码久久综合东京热| 2021最新久久久视精品爱 | 久久亚洲精品无码aⅴ大香| 久久精品国产99久久香蕉| 性做久久久久久久久老女人| 久久中文字幕精品| 精品久久久噜噜噜久久久| 国产一区二区精品久久岳| 久久人人爽人人爽人人片AV不| 久久婷婷五月综合97色| 国产精品九九久久精品女同亚洲欧美日韩综合区 | 亚洲精品无码久久久久sm| 色综合久久综合网观看| 中文精品99久久国产 | 一级女性全黄久久生活片免费| 亚洲av伊人久久综合密臀性色| 成人a毛片久久免费播放| 久久久久久伊人高潮影院| 国产激情久久久久影院小草| 久久久久亚洲精品日久生情| 久久亚洲精品视频| 亚洲国产精品无码久久久秋霞2| 四虎国产精品免费久久久| 色欲久久久天天天综合网| 国产精品久久久久久久午夜片| 午夜久久久久久禁播电影| 久久精品国产99久久丝袜| 久久夜色tv网站| 久久精品无码专区免费东京热| 性欧美大战久久久久久久| 日本道色综合久久影院| 久久99国产综合精品女同| 综合网日日天干夜夜久久| 久久国产视屏| 久久精品亚洲精品国产欧美| 久久99国产精一区二区三区| 久久精品国产亚洲av高清漫画 | 久久午夜无码鲁丝片| 亚洲日韩中文无码久久| 久久精品国产男包|