Tuesday, June 05, 2007

Stoer-Wagner算法

Stoer-Wagner算法是用来计算无向图的全局最小割的,理论上复杂度可以为O(|E|+|V|log|V|)。我的实现不是最好的,但觉得还行吧。

网友的好文章:最小割Stoer-Wagner算法

题目是百度06年的复赛题,星球大战。可以在POJ上练习,POJ2914。

相关论文和偶的代码,可点此下载

Stoer-Wagner算法的实现:


#include <iostream>
#include <algorithm>
using namespace std;

#define initSet(n,Arr) for(int i=0;i<n;++i)Arr[i]=i;
#define MAX 1<<30;
int graph[600][600];

// Stoer-Wagner Algorithm
int globalMinCut(int n){
// A is A set for Stoer-Wagner Algorithm
bool* A=new bool[n];
// V is vertex index
int* V=new int[n];
int* W=new int[n];

initSet(n,V);

int best=MAX;
while(n>1){

//the most tightly connected vertex.
int maxj=1;

// initialize set A and other vertex's weight
A[V[0]] = true;
for(int i=1; i<n; ++i){
A[V[i]]=false;
W[i]=graph[V[0]][V[i]];

if(W[i]>W[maxj])
maxj=i;
}

// find a min-cut
int prev=0,buf=n;
while(--buf){
// add it to A
A[V[maxj]]=true;

if(buf==1){
// update min cut
best=min(best,W[maxj]);

// merge prev and last vertex
for(int k=0; k<n; ++k)
graph[V[k]][V[prev]]=(graph[V[prev]][V[k]]
+=graph[V[maxj]][V[k]]);
V[maxj]=V[--n];
}
prev=maxj;
maxj=-1;

// update the weights
for(int j=1; j<n; ++j)
if(!A[V[j]]){
W[j]+=graph[V[prev]][V[j]];

if(maxj<0 || W[j]>W[maxj])
maxj=j;
}
}
}

delete[] A;
delete[] V;
delete[] W;
return best;
}


int main(){
// n - vertex number
// m - edge number
int n,m;

while(scanf("%d %d",&n,&m)==2){
memset(graph,0,sizeof(graph)/sizeof(bool));

// v-w is an edge with c weight
int v,w,c;

while(m--){
scanf("%d %d %d",&v,&w,&c);
graph[v][w]+=c;
graph[w][v]+=c;
}

// output min cut
printf("%d\n",globalMinCut(n));
}
}


No comments: