Bzoj1050 AHOI2006旅行 并查集

比较简单的题目

就是在无向图上求一条st的路使得最大权和最小权的比值min

因为数据范围不大所以直接暴力就可以过

只需要按边权排序然后依次加入并查集维护连通性就可以了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define MAX 5009

using namespace std;

int father[MAX];
int n,m,s,t;

struct wbysr
{
	int num,value;
	int from,to;
}d[MAX];

void add(int num,int from,int To,int weight)
{
	d[num].value=weight;
	d[num].from=from;
	d[num].to=To;
}

int find(int x)
{
	if(father[x]==x)
		return x;
	father[x]=find(father[x]);
	return father[x];
}

void Union(int x,int y)
{
	int a1=find(x),a2=find(y);
	if(a1!=a2)
		father[a1]=a2;
	return;
}

int gcd(int x,int y)
{
	if(!y)
		return x;
	return gcd(y,x%y);
}

bool cmp(wbysr a1,wbysr a2)
{
	return a1.value<a2.value;
}

int main()
{
	scanf("%d%d",&n,&m);
	rep(i,1,m)
	{
		int a1,a2,a3;
		scanf("%d%d%d",&a1,&a2,&a3);
		add(i,a1,a2,a3);
	}
	scanf("%d%d",&s,&t);
	sort(d+1,d+1+m,cmp);
	rep(i,1,n)
		father[i]=i;
	int ans1=999999,ans2=1;
	rep(i,1,m)
	{
		rep(i,1,n)
			father[i]=i;
		for(int j=i;j<=m;j++)
		{
			Union(d[j].from,d[j].to);
			if(find(s)==find(t))
			{
				if(ans2*d[j].value<ans1*d[i].value)
					ans1=d[j].value,ans2=d[i].value;
				break;
			}
		}
	}
	if(999999==ans1)
		printf("IMPOSSIBLE\n");
	else
	{
		int u=gcd(ans1,ans2);
		if(ans2==u)
			printf("%d\n",ans1/u);
		else
			printf("%d/%d\n",ans1/u,ans2/u);
	}
	return 0;
}

Bzoj1050 AHOI2006旅行 并查集,布布扣,bubuko.com

Bzoj1050 AHOI2006旅行 并查集

原文：http://blog.csdn.net/wbysr/article/details/22980501