@[Andy_Li](/user/361266) 注意特判 s,t 只需一条边就能联通的情况
by LV06 @ 2022-11-15 21:17:38
@[Gravel](/user/558597) 咋改？
by Andy_Li @ 2022-11-15 21:52:45
60行j从i开始即可
```
//AC代码
#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;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;
}
```cpp
by smqa @ 2022-11-19 12:19:24
@[Andy_Li](/user/361266)
by smqa @ 2022-11-19 12:19:48
@[alpha008](/user/569971) 栓Q
by Andy_Li @ 2022-11-19 12:39:57
嗨
by yanbinmu @ 2022-11-20 11:35:25