posts - 7,comments - 3,trackbacks - 0
<2025年4月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

常用链接

留言簿(1)

随笔分类(7)

随笔档案(7)

文章分类(19)

文章档案(19)

搜索

  •  

最新评论

阅读排行榜

评论排行榜

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 阅读(211) 评论(0)  编辑 收藏 引用 所属分类: 网络流

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