poj 1679 The Unique MST 次小生成树

SoL：裸的次小生成树。。。

推荐：KuangBin巨巨的博客 模版 + 详解      http://www.cnblogs.com/kuangbin/p/3147329.html

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int maxn = 100 + 10;
const int INF = 0x3f3f3f3f;

int ans;
bool vis[maxn];
int lowc[maxn];
int pre[maxn];
int Max[maxn][maxn];
bool used[maxn][maxn];

int Prim(int cost[][maxn],int n)
{
	int ans=0;
	memset(vis,false,sizeof(vis));
	memset(Max,0,sizeof(Max));
	memset(used,false,sizeof(used));
	vis[0]=true;
	pre[0]=-1;
	for(int i=1;i<n;i++)
	{
		lowc[i]=cost[0][i];
		pre[i]=0;
	}
	lowc[0]=0;
	for(int i=1;i<n;i++)
	{
		int minc=INF;
		int p=-1;
		for(int j=0;j<n;j++)
			if(!vis[j]&&minc>lowc[j])
			{
				minc=lowc[j];
				p=j;
			}
		if(minc==INF) return -1;
		ans+=minc;
		vis[p]=true;
		used[p][pre[p]]=used[pre[p]][p]=true;
		for(int j=0;j<n;j++)
		{
			if(vis[j])
				Max[j][p]=Max[p][j]=max(Max[j][pre[p]],lowc[p]);
			if(!vis[j]&&lowc[j]>cost[p][j])
			{
				lowc[j]=cost[p][j];
				pre[j]=p;
			}
		}
	}
	return ans;
}

int smst(int cost[][maxn],int n)
{
	int Min=INF;
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
		if(cost[i][j]!=INF&&!used[i][j])
			Min=min(Min,ans+cost[i][j]-Max[i][j]);
	if(Min==INF)  return -1;
	return Min;
}

int cost[maxn][maxn];

int T,n,m;

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		int u,v,w;
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
			{
				if(i==j) cost[i][j]=0;
				else cost[i][j]=INF;
			}
		while(m--)//0开始 
		{
			scanf("%d%d%d",&u,&v,&w);
			u--,v--;
			cost[u][v]=cost[v][u]=w;
		}
		ans=Prim(cost,n);
		if(ans==-1)
		{
			printf("Not Unique!\n");
			continue;
		}
		if(ans==smst(cost,n))
			printf("Not Unique!\n");
		else
			printf("%d\n",ans);
	}
	return 0;
}

poj 1679 The Unique MST 次小生成树

原文：http://blog.csdn.net/imutzcy/article/details/18444193