3158335_ac_1547ms_380k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, m;
int map[101][101];
int visited[101];
int cnt;
int edge[10000];

void dfs(int v)
{
	int i;

	cnt++;
	visited[v] = 1;
	for(i = 0; i < n; i++)
	{
		if(map[v][i]!=0&&!visited[i])
			dfs(i);
	}
}

int up, low;

void Dfs(int v)
{
	int i;

	cnt++;
	visited[v] = 1;
	for(i = 0; i < n; i++)
	{
		if(!visited[i]&&map[v][i] >= low&&map[v][i] <= up)
			Dfs(i);
	}
}

int check(int h)
{
	int i;

	for(i = 0; i < m; i++)
	{
		if(i&&edge[i]==edge[i-1])
			continue;
		low = edge[i];
		up = low+h;
		cnt = 0;
		memset(visited,0,sizeof(visited));
		Dfs(0);
		if(cnt==n)
			return 1;
	}
	return 0;
}

int main()
{
	int i;
	int a, b, w;
	int min, max, mid;

	while(scanf("%d%d",&n,&m)==2)
	{
		if(n==0&&m==0)
			break;
		memset(map,0,sizeof(map));
		for(i = 0; i < m; i++)
		{
			scanf("%d%d%d",&a,&b,&w);
			a--;b--;
			map[a][b] = map[b][a] = w;
			edge[i] = w;
		}
		cnt = 0;
		memset(visited,0,sizeof(visited));
		dfs(0);
		if(cnt!=n)
		{
			puts("-1");
			continue;
		}
		sort(edge,edge+m);
		min = 0;
		max = 10000;
		while(min < max)
		{
			mid = (min+max)>>1;
			if(check(mid))
				max = mid;
			else
				min = mid+1;
		}
		printf("%d\n",min);
	}
	return 0;
}