POJ 2914 Minimum Cut 最小割图论

Description

Input

Output

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

本题是06年百度之星半决赛的题目，图论的最小割问题。算是图论高级内容吧。

Stoer Wager算法，当中的难点是：

1 逐条边查找最大的边的权值-过程有点想Prime算法，只是实际上不是Prime算法，由于目的并非最大生成树，而是须要把一个顶点的全部边都加起来。把这些边去掉，就是这个顶点的割点值了。那么就须要遍历整个图，到了最后一个节点才干保证是找到了这个节点的全部边。

2 缩点：所谓缩点就是把最后一个节点去掉，同一时候保留其边值信息，实际就是保留这个顶点的和其它顶点相连的最小边值。

比較难理解的，一般写这个题解报告的博客，一个是要么直接抄模板了。二是要么没有讲解；三个是有了几句讲解了。结果都没理解好，甚至错误；

也是非常难说清楚的一个题目，看看我具体凝视的程序吧。

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <algorithm>
using namespace std;

const int MAX_N = 501;
int gra[MAX_N][MAX_N];//矩阵表示图

bool shrinkedVertices[MAX_N];//标志那些顶点已经被缩点了
bool vis[MAX_N];//标志当前那些节点已经訪问了
int dis[MAX_N];//记录最大距离
int lastSec, last;//记录每次最后cut边的两个顶点
int getLastCut(int leftVertices, int n)//每次计算剩下多少没缩点的顶点计算就可以
{
	fill(dis, dis+n, 0);
	fill(vis, vis+n, false);
	int curVer = 0;//curVer代表当前选取的顶点，初始为选取0顶点
	lastSec = last = 0;

	//循环的主要作用的把一个顶点的全部边都加起来。仅仅有在最后一次选择的时候才干确保最后一个顶点的全部边都加起来了。
	for (int i = 1; i < leftVertices; i++)
	{//操作的是边。边比顶点少1的，故此i从1開始，不是从0開始
		for (int v = 1; v < n; v++)
		{//0顶点已经最先选择了，故此v从1開始，不是从0開始
			if (!vis[v] && !shrinkedVertices[v]) dis[v] += gra[v][curVer];
		}//主要是把一个顶点的全部边都加起来
		int maxCut = 0;
		//选取当前最大的割边。未到最后一点。不能保证是真正的割边
		for (int v = 1; v < n; v++)
		{
			if (!vis[v] && !shrinkedVertices[v] && dis[v] > maxCut)
			{
				maxCut = dis[v];
				curVer = v;
			}
		}
		if (!maxCut) return 0;//本来就是分隔图，割边能够为零了。
		vis[curVer] = true;		lastSec = last; last = curVer;//逐次保存最后两个顶点	}	return dis[last];}int Stoer_Wagner(int n){	fill(shrinkedVertices, shrinkedVertices+n, false);	int minCut = INT_MAX;	for (int i = n; i > 1; i--)	{				minCut = min(minCut, getLastCut(i, n));		if (!minCut) return 0;		shrinkedVertices[last] = true;		for (int v = 0; v < n; v++)		{			if (!shrinkedVertices[v])				gra[lastSec][v] = gra[v][lastSec] += 				min(gra[v][last], gra[last][lastSec]);//事实上缩点就是保留当中一段边，须要保留最小值边，确保是最小割。		}	}	return minCut == INT_MAX? 0 : minCut;}int main(){	int N, M, u, v, w;	while (~scanf("%d %d", &N, &M))	{		for (int i = 0; i < N; i++)		{			for (int j = 0; j < N; j++)			{				gra[i][j] = 0;			}		}		for (int i = 0; i < M; i++)		{			scanf("%d %d %d", &u, &v, &w);			gra[u][v] = gra[v][u] += w;		}		printf("%d\n", Stoer_Wagner(N));	}	return 0;}

只是上面程序的效率不高。那么能够优化一下。优化的主要方法是，利用一个数组保存好剩下的顶点，那么缩点的时候直接删除这个顶点。就不用下一次还须要遍历推断这个顶点。

这样优化了常数项，实际执行时间快了2到3倍左右，效果非常好。

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <algorithm>
using namespace std;

const int MAX_N = 501;
int gra[MAX_N][MAX_N];
int vps[MAX_N];
bool vis[MAX_N];
int dis[MAX_N];
int last, sec;

int getLastCut(int V)
{
	fill(vis, vis+V, false);
	fill(dis, dis+V, 0);
	last = sec = 0;
	int id = 0;
	for (int i = 1; i < V; i++)
	{
		int v = vps[id];
		for (int j = 1; j < V; j++)
		{
			if (!vis[j]) dis[j] += gra[v][vps[j]];
		}
		int m = 0;
		for (int j = 1; j < V; j++)
		{
			if (!vis[j] && m < dis[j]) m = dis[j], id = j;
		}
		if (!m) return 0;
		vis[id] = true;
		sec = last; last = vps[id];
	}
	swap(vps[id], vps[V-1]);
	return dis[id];
}

int Stoer_wagner(int n)
{
	for (int i = 0; i < n; i++) vps[i] = i;
	int minCut = INT_MAX;
	for (int V = n; V > 1; V--)
	{
		minCut = min(minCut, getLastCut(V));
		if (!minCut) return 0;
		for (int i = 0; i < V; i++)
		{
			int v = vps[i];
			gra[v][sec] = gra[sec][v] += min(gra[v][last], gra[last][sec]);
		}
	}
	return minCut == INT_MAX? 0 : minCut;
}

int main()
{
	int Ver, Edge, u, v, w;
	while (~scanf("%d %d", &Ver, &Edge))
	{
		for (int i = 0; i < Ver; i++)
			for (int j = 0; j < Ver; j++)
				gra[i][j] = 0;

		for (int i = 0; i < Edge; i++)
		{
			scanf("%d %d %d", &u, &v, &w);
			gra[u][v] = gra[v][u] += w;
		}
		printf("%d\n", Stoer_wagner(Ver));
	}
	return 0;
}