BZOJ 1050 枚举+并查集

时间:2024-06-09 12:36:14

思路:

枚举最大边 像Kruskal一样加边 每回更新一下 就搞定了…

//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10050
int n,m,s,t,fx,fy,f[N],stk[N],top,vis[N],recx,recy;
double ans=666666.0;
struct Node{int x,y,z;}node[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
bool cmp(Node a,Node b){return a.z<b.z;}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].z);
fx=find(node[i].x),fy=find(node[i].y);
if(fx!=fy)f[fx]=fy;
}
scanf("%d%d",&s,&t);
if(find(s)!=find(t)){puts("IMPOSSIBLE");return 0;}
sort(node+1,node+1+m,cmp);
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++)f[j]=j;
for(int j=i;j;j--){
fx=find(node[j].x),fy=find(node[j].y);
if(fx!=fy)f[fx]=fy;
if(find(s)==find(t)){
if(ans>1.0*node[i].z/node[j].z){
ans=1.0*node[i].z/node[j].z;
recx=node[i].z,recy=node[j].z;
}
break;
}
}
}
int GCD=gcd(recx,recy);
if(GCD!=recy)printf("%d/%d",recx/GCD,recy/GCD);
else printf("%d\n",recx/recy);
}

BZOJ 1050 枚举+并查集