哪位巨佬能帮忙找哪里RE了(90分)
查看原帖
哪位巨佬能帮忙找哪里RE了(90分)
216909
Viktley楼主2020/7/21 07:54
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
using namespace std;
const double MAX=2147483647;
const int N=1e6;
struct node
{
	int u,v,w;
} edge[50010];
int father[5010],n,m,t,s,minspeed,maxspeed;
double minn=MAX;
int find(int a){return a==father[a]?a:father[a]=find(father[a]);}
bool cmp(node a,node b){return a.w<b.w;}
void unionn(int x,int y)
{
	int a=find(x),b=find(y);
	if(a!=b) father[a]=b;
}
int gcd(int x,int y)
{
	int r=x%y;
	while(r) x=y,y=r,r=x%y; 
	return y;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) father[i]=i;
	for(int i=1;i<=m;i++) scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
	scanf("%d%d",&s,&t);
	sort(edge+1,edge+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++) father[j]=j;
		edge[0].u=0;
		for(int j=i;j<=m;j++)
		{
			if(find(edge[j].u)!=find(edge[j].v)) unionn(edge[j].u,edge[j].v);
			if(find(s)==find(t)) {edge[0].u=j;break;}
		}
		double sum=edge[edge[0].u].w*1.0/edge[i].w;
		if(edge[0].u&&sum<minn)
		{
			int temp=gcd(edge[i].w,edge[edge[0].u].w);
			minn=sum;
			minspeed=edge[i].w/temp,maxspeed=edge[edge[0].u].w/temp;	
		}
	}
	if(minn==MAX) printf("IMPOSSIBLE\n");
	if(!(maxspeed%minspeed)) printf("%d\n",maxspeed/minspeed);
	else printf("%d/%d",maxspeed,minspeed);
	return 0;
}
2020/7/21 07:54
加载中...