网站建设主要步骤,莆田市城厢区建设局网站,网站首页模板制作,seo做的好的网站有哪些HYSBZ - 1050(旅行comf Java实现) 原题地址 解法#xff1a;枚举每一条边#xff0c;对于这条边#xff0c;我们需要找到集合中和其值相差最小的最大边#xff0c;这个集合是指与包括i边在内的ST联通集。对于这一要求#xff0c;我们只需对所有的边进行从小到大的排序枚举每一条边对于这条边我们需要找到集合中和其值相差最小的最大边这个集合是指与包括i边在内的ST联通集。对于这一要求我们只需对所有的边进行从小到大的排序那么从i边开始一条条地加入并查集一旦形成上述的联通集立刻停止。 import java.io.*;
import java.util.*;
public class Main{private static class edge{int x,y,v;}private static class cmp implements Comparatoredge{Overridepublic int compare(edge a,edge b){return a.vb.v?-1:1;}}private static int fa[]new int[505];private static int Find(int x){if(fa[x]-1) return x;return fa[x]Find(fa[x]);}private static int gcd(int a,int b){return b0?a:gcd(b,a%b);}private static final int N50005;private static edge e[]new edge[N];public static void main(String[] args){int n,m,s,t;Scanner scnew Scanner(new InputStreamReader(System.in));nsc.nextInt();msc.nextInt();for(int i0;im;i){e[i]new edge();e[i].xsc.nextInt();e[i].ysc.nextInt();e[i].vsc.nextInt();}ssc.nextInt();tsc.nextInt();Arrays.sort(e,0,m,new cmp());int x10,y10;for(int i0;im;i){int ma-1;Arrays.fill(fa,-1);for (int ji; jm; j){int f1Find(e[j].x),f2Find(e[j].y);if (f1f2) continue;fa[f1]f2;if (Find(s)Find(t)){mae[j].v;break;}}if (ma-1i0){System.out.printf(IMPOSSIBLE\n);System.exit(0);}if (ma-1) break;if (x10||x1*e[i].vma*y1){x1ma;y1e[i].v;}}int xgcd(x1,y1);if (xy1) System.out.printf(%d\n,x1/y1);else System.out.printf(%d/%d\n,x1/x,y1/x);sc.close();}
} 转载于:https://www.cnblogs.com/zsyacm666666/p/6670458.html
