LA 3887 - Slim Span 枚举+MST

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1888

题目大意：

定义Slim span为一幅无向图的生成树，且它的值为最大的权减最小的权。现在让你求最小的Slim span

思路：

固定最小的边，枚举最大的边。然后看看哪个大就可以了~

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100+10;
int n,m,fa[MAXN];
int find(int cur)
{
	return cur==fa[cur]? cur:fa[cur]=find(fa[cur]);
}

struct edge
{
	int from,to,val;
	bool operator<(const edge& x)const {
		return val<x.val;
	}

}e[MAXN*MAXN];

void init()
{
	for(int i=1;i<=n;i++)
		fa[i]=i;
}

int kruskal(int i)
{
	int res=0;
	int cnt=0;
	for(;i<m;i++)  
	{  
		int x=e[i].from,y=e[i].to;  
		int root_x=find(x),root_y=find(y);  
		if(root_x==root_y)   continue;  
		cnt++;
		fa[root_x]=root_y;  
		res=e[i].val;		  
	} 
	if(cnt!=n-1)
		return -1;
	return res;
}

int main()
{
	while(~scanf("%d%d",&n,&m),n||m)
	{
		for(int i=0;i<m;i++)
			scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].val);
		sort(e,e+m);
		init();
		int ans=kruskal(0);
		if(ans==-1)
		{
			printf("-1\n");
			continue;
		}
		ans-=e[0].val;
		for(int i=1;i<m;i++)
		{
			init();
			int res=kruskal(i);			 //固定最小边，枚举最大边
			if(res==-1) break;
			ans=min(ans, res-e[i].val);    
		}
		printf("%d\n",ans);
	}
	return 0;
}

LA 3887 - Slim Span 枚举+MST

原文：http://blog.csdn.net/murmured/article/details/18895111