这是建空间后做的第一道题啊= =好水
排序，枚举最小边，然后并查集求出联通时的最大边
或者排次序，从小到大插边，如果插边时最小的边拿掉不会使s与t不联通，就删去。
code：
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;
struct node{
int x,y,dist;
}a[5010];int n,m,s,t,f[510],ansi,ansa;
bool cmp(node x,node y){return x.dist<y.dist;}
int find(int x){if (x!=f[x]) f[x]=find(f[x]);return (f[x]);}
int gcd(int x,int y){
if (!y) return x;
return gcd(y,x %y);
}int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].dist);
sort(a+1,a+1+m,cmp);
scanf("%d%d",&s,&t);
ansi=a[1].dist;ansa=40000;
for (int i=1;i<=n;i++) f[i]=i;
for (int i=1;i<=m;i++) {
int x=find(a[i].x),y=find(a[i].y);
if (x!=y) f[x]=y;
x=find(s);y=find(t);
if (x==y) {
ansa=a[i].dist;
break;
}
}
if (ansa==40000) {printf("IMPOSSIBLE\n");return 0;}
for (int i=2;i<=m;i++) {
for (int j=1;j<=n;j++) f[j]=j;
for (int j=i;j<=m;j++) {
int x=find(a[j].x),y=find(a[j].y);
if (x!=y) f[x]=y;
x=find(s);y=find(t);
if (x==y) {
if (ansa*1.0/ansi>a[j].dist*1.0/a[i].dist) {ansa=a[j].dist;ansi=a[i].dist;}
break;
}
}
}
int t=gcd(ansa,ansi);
if (ansa*1.0/ansi==ansa/ansi) printf("%d\n",ansa/ansi);
else printf("%d/%d",ansa/t,ansi/t);
return 0;
} |