无向图最小割.cpp

本人参加ACM竞赛使用的一些算法模板

/*************************************************************
*
*	Stoer-Wagner Minimum Cut求无源无汇的无向网络最小割
*   (poj	2914	Minimum Cut)
*************************************************************/
#include <iostream>
#include <cstdio>
using namespace std;
int const MAXN = 512;
int const INF = 123456789;

int graph[MAXN][MAXN], vertex[MAXN], weight[MAXN];
//容量矩阵和节点数组
bool a[MAXN];

int minCut( int n )
{//传入n为节点数
    for( int i = 0; i < n; i++ )
	{
		vertex[i] = i;
	}
    int best = INF;
    while( n > 1 )
    {
        a[vertex[0]] = true;
        for( int i = 1; i < n; i++ )
        {
            a[vertex[i]] = false;
            weight[i] = graph[vertex[0]][vertex[i]];
        }
        int prev = vertex[0];
        for( int i = 1; i < n; i++ )
        {
            int t = -1;
            for( int j = 1; j < n; j++ )
            {
                if( !a[vertex[j]] && ( t < 0 || weight[j] > weight[t] ) )
                {
                    t = j;
				}
			}
		    a[vertex[t]] = true;
            if( i == n - 1 )
            {
                best <?= weight[t];
                for( int i = 0; i < n; i++ )
                    graph[vertex[i]][prev] =
					graph[prev][vertex[i]] += graph[vertex[t]][vertex[i]];
                vertex[t] = vertex[--n];
                break;
            }
            prev = vertex[t];
            for( int j = 1; j < n; j++ )
			{
				if( !a[vertex[j]] )
				{
                	weight[j] += graph[vertex[t]][vertex[j]];
				}
			}
        }
    }
    return best;
}
int N, M;
bool read_data(){
	if(scanf("%d %d", &N, &M) != EOF) {
		for (int i = 0; i < N; ++i){
			for (int j = 0; j < N; ++j){
				graph[i][j] = 0;
			}
		}
		int u, v, w;
		while (M--){
			scanf("%d %d %d", &u, &v, &w);
			graph[u][v] = graph[v][u] += w;
		}
		return true;
	}
	return false;
}
int main()
{
    while (read_data() ){
		int ans = minCut(N);
		printf("%d\n", ans);
	}
    return 0;
}