HYSBZ - 1050(旅行comf 并查集Java实现)

HYSBZ - 1050(旅行comf Java实现)

解法：枚举每一条边，对于这条边，我们需要找到集合中和其值相差最小的最大边，这个集合是指与包括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 Comparator<edge>{

        @Override

        public int compare(edge a,edge b){

            return a.v<b.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 b==0?a:gcd(b,a%b);

    }

    private static final int N=5000+5;

    private static edge e[]=new edge[N];

    public static void main(String[] args){

        int n,m,s,t;

        Scanner sc=new Scanner(new InputStreamReader(System.in));

        n=sc.nextInt();m=sc.nextInt();

        for(int i=0;i<m;i++){

            e[i]=new edge();

            e[i].x=sc.nextInt();

            e[i].y=sc.nextInt();

            e[i].v=sc.nextInt();

        }

        s=sc.nextInt();

        t=sc.nextInt();

        Arrays.sort(e,0,m,new cmp());

        int x1=0,y1=0;

        for(int i=0;i<m;i++){

            int ma=-1;

            Arrays.fill(fa,-1);

            for (int j=i; j<m; j++){

                int f1=Find(e[j].x),f2=Find(e[j].y);

                if (f1==f2) continue;

                fa[f1]=f2;

                if (Find(s)==Find(t)){

                    ma=e[j].v;

                    break;

                }

            }

            if (ma==-1&&i==0){

                System.out.printf("IMPOSSIBLE\n");

                System.exit(0);

            }

            if (ma==-1) break;

            if (x1==0||x1*e[i].v>ma*y1){

                    x1=ma;y1=e[i].v;

            }

        }

        int x=gcd(x1,y1);

        if (x==y1) System.out.printf("%d\n",x1/y1);

        else System.out.printf("%d/%d\n",x1/x,y1/x);

        sc.close();

    }

}

巴特西

HYSBZ - 1050(旅行comf 并查集Java实现)

HYSBZ - 1050(旅行comf Java实现)

最新文章

热门文章