90分,第一点WA求调
查看原帖
90分,第一点WA求调
361266
Andy_Li楼主2022/11/15 21:10
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
int fa[1000010],vis[100010];
struct node
{
	int x,y,z;
}a[1000010];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
void make(int x,int y)
{
	int xx=find(x),yy=find(y);
	if(xx==yy)
		return ;
	fa[yy]=xx;
}
int cmp(node x,node y)
{
	return x.z>y.z;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int n,m,s,t,p1=0,p2=0;
	double ans=100000000;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].z;
		make(a[i].x,a[i].y);
	}
	cin>>s>>t;
	if(fa[s]!=fa[t])
	{
		cout<<"IMPOSSIBLE";
		return 0;
	}
	for(int i=1;i<=n;i++)
		fa[i]=i;
	sort(a+1,a+m+1,cmp);
//	for(int i=1;i<=m;i++)
//		cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].z<<endl;
	for(int i=1;i<m;i++)
	{
		int k=0;
		make(a[i].x,a[i].y);
		for(int j=i+1;j<=m;j++)
		{
			make(a[j].x,a[j].y);
			if(find(fa[s])==find(fa[t]))
			{
				k=j;
				break;
			}
		}
		for(int j=1;j<=n;j++)
			fa[j]=j;
		if(k==0)
			continue;
		if(double(a[i].z*1.0/a[k].z*1.0)<ans)
		{
			ans=double(a[i].z*1.0/a[k].z*1.0);
			p1=a[i].z;
			p2=a[k].z;
		}
	}
	if(p1%p2==0)
		cout<<p1/p2;
	else
		cout<<p1/(__gcd(p1,p2))<<"/"<<p2/(__gcd(p1,p2));
	return 0;
}

2022/11/15 21:10
加载中...