洛谷题解 P2502 【[HAOI2006]旅行】

由于此题边数比较小，所以可以先给边排个序，然后跑m遍最小生成树，每跑一次删除一条边，找最优解。

防TLE技巧

把边按从小到大的顺序排好，那么只要当前无法联通，那么后面也无法联通

最优解找法

double tmp=(1.0*e[i].w)/(1.0*e[j].w);

//因为边是有序的，所以当前的第一条边是最大的，保证能联通的最后一条边就是最小的（详细的自己理解）

if(tmp<ans) a=e[i].w,b=e[j].w,ans=tmp;

//与当前的最优解进行比较

分数的处理技巧

设a和b是最后的结果，那么当b能整除a时，直接输出商

否则就求一遍最大公约数，把a与b分别除以这个最大公约数，输出结果

代码

#include<bits/stdc++.h>

using namespace std;

const int MAXN=500+10;

const int MAXM=5000+10;

int n,m,s,t;

struct Node

{

	int u,v,w;

}edge[MAXM];

int f[MAXN];

int ans1,ans2;

inline int find(int k)

{

	if(f[k]==k)return k;

	else return f[k]=find(f[k]);

}

inline bool cmp(Node u,Node v)

{

	return u.w<v.w;

}

inline void init()//每次的并查集初始化

{

	for(int i=1;i<=n;i++)f[i]=i;

}

inline int read()

{

	int tot=0,f=1;

	char c=getchar();

	while(c<'0'||c>'9')

	{

		if(c=='-')f=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9')

	{

		tot=tot*10+c-'0';

		c=getchar();

	}

	return tot*f;

}

inline int gcd(int x,int y)//求最大公约数

{

	if(y>x)return gcd(y,x);

	if(y==0)return x;

	return gcd(y,x%y);

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=m;i++)

	{

		edge[i].u=read();

		edge[i].v=read();

		edge[i].w=read();

	}

	s=read();t=read();

	sort(edge+1,edge+1+m,cmp);

	int now;

	for(int i=1;i<=m;i++)

	{

		init();

		/*for(int i=1;i<=n;i++)cout<<f[i]<<" ";

		cout<<endl;*/

		for(now=i;now<=m;now++)

		{

			int fx=find(edge[now].u),fy=find(edge[now].v);

			//cout<<fx<<" "<<fy<<endl;

			if(fx==fy)continue;

			f[fx]=fy;

			if(find(s)==find(t))break;

		}

		/*for(int i=1;i<=n;i++)cout<<f[i]<<" ";

		cout<<endl;*/

		if(i==1&&find(s)!=find(t))

		{

			cout<<"IMPOSSIBLE\n";

			return 0;

		}

		if(find(s)!=find(t))break;

		if(ans1*edge[i].w>=ans2*edge[now].w)ans1=edge[now].w,ans2=edge[i].w;

	}

	//cout<<ans1<<" "<<ans2<<endl;

	if(ans2%ans1==0)

	{

		cout<<ans2/ans1<<endl;

		return 0;

	}

	int gcdd=gcd(ans1,ans2);

	cout<<ans1/gcdd<<"/"<<ans2/gcdd<<endl;

	return 0;

}

巴特西

洛谷题解 P2502 【[HAOI2006]旅行】

最新文章

热门文章

巴特西

洛谷 题解 P2502 【[HAOI2006]旅行】

最新文章

热门文章

洛谷题解 P2502 【[HAOI2006]旅行】