算法:最小生成树

早已会各位大佬们可超越了QwQ,today,we will use a magical
algorithm!let is go!

问题

让起部分Connections,即Connections类,找到有能够用持有市都连接起来并且花费最小之限。
假使说好拿兼具都都连接起来,则赶回这个连续方式;不然的话返回一个空列表。

非露摆了(也没得显摆),今天咱们之所以Kruskal算法来打消这道题。

注意事项

回到cost最小的连方式,如果cost相同就本city1进行排序,如果city1也一致那么就是按city2进行排序。
辅助类:

public class Connection {
    public String city1;
    public String city2;
    public int cost;
    public Connection(String city1, String city2, int cost) {
        this.city1 = city1;
        this.city2 = city2;
        this.cost = cost;
    }
}
  1. 定义

    int fa[1000100],i,j,k,n,m,s,ans;//基本变量:)
    struct eige{

    int x,y,z;

    }a[1000100];//主要是以排序

样例

给出 connections = [“Acity”,”Bcity”,1], [“Acity”,”Ccity”,2],
[“Bcity”,”Ccity”,3]
返回 [“Acity”,”Bcity”,1], [“Acity”,”Ccity”,2]

 

思路

主题一看问题就亮是无向图的绝小生成树题材,而解决这题目时有发生2个名的算法,Prim算法和Kruskal算法,但是Prim算法在生同样权值的边时会失灵,所以此题只能用Kruskal算法来化解。
Kruskal算法的机要思想是把边按照权值从小至大排序,然后挨家挨户取出最小限度。

 

实现

public List<Connection> lowestCost(List<Connection> connections) {
        // Write your code here
        connections.sort(new Comparator<Connection>() {
            @Override
            public int compare(Connection o1, Connection o2) {
                if (o1.cost != o2.cost) {
                    return o1.cost - o2.cost;
                } else {
                    if (o1.city1.equals(o2.city1)) {
                        return o1.city2.compareTo(o2.city2);
                    } else {
                        return o1.city1.compareTo(o2.city1);
                    }
                }
            }
        });

        Set<String> points = new HashSet<>();
        for (Connection connection : connections) {
            points.add(connection.city1);
            points.add(connection.city2);
        }

        List<Connection> result = new ArrayList<>();
        List<Set<String>> pointSets = new ArrayList<>();
        for (String point : points) {
            Set<String> set = new HashSet<>();
            set.add(point);
            pointSets.add(set);
        }

        for (Connection connection : connections) {
            String start = connection.city1;
            String end = connection.city2;
            int startIndex = -1;
            int endIndex = -1;

            int i = 0;
            for (Set<String> point : pointSets) {
                if (point.contains(start)) {
                    startIndex = i;
                }
                if (point.contains(end)) {
                    endIndex = i;
                }
                i++;
            }

            if (startIndex < 0 || endIndex < 0) {
                return new ArrayList<>();
            }

            // 比较startIndex和endIndex大小的原因:如果先删除HasHMap较小index的元素,再删除较大Index元素时,会造成数组越界
            // 所以hashSet执行多个remove操作的时候,一定要从后往前删
            if (startIndex > endIndex) {
                Set<String> startSet = pointSets.get(startIndex);
                pointSets.remove(startIndex);
                Set<String> endSet = pointSets.get(endIndex);
                pointSets.remove(endIndex);
                startSet.addAll(endSet);
                pointSets.add(startSet);
                result.add(connection);
            } else if (startIndex < endIndex) {
                Set<String> endSet = pointSets.get(endIndex);
                pointSets.remove(endIndex);
                Set<String> startSet = pointSets.get(startIndex);
                pointSets.remove(startIndex);
                startSet.addAll(endSet);
                pointSets.add(startSet);
                result.add(connection);
            }

        }

        if (pointSets.size() > 1) {
            return new ArrayList<>();
        }

        return result;
    }

倘文章针对性你发出救助的话,不要忘记了打赏小编哟

  1. 排序函数定义
int cmp(eige u,eige v){
return u.z<v.z;//将边长从小到大排好;)
}

 

连下给咱联合来开一样起伟大的事情———并查集!(详见博客)
[接触及时为堪](http://baidu.apphb.com/?q=并查集),
盖只要简单个点当不同集合则统一为培训,否则跳了。

始于查集

int find(int x){
if(x==fa[x]){//是不是同一个boss
return x;
}
else return fa[x]=find(fa[x]);
}

 

哼了,让我们打主程序吧ヾ(✿゚▽゚)ノ▄︻┻┳══━一

 //输入跳过
sort(a+1,a+1+m,cmp);//排个序
for(i=1;i<=n;i++){
fa[i]=i;//所有人的父节点是自己
}
for(i=1;i<=m;i++){
if(find(a[i].x)!=find(a[i].y)){//看看两个人在不在同一集合
fa[find(a[i].x)]=find(a[i].y);//不是则合并
s++;
ans+=a[i].z;//累加树边长度
if(s>=n-1){
break;
}
}
}
if(s<n-1){
cout<<"orz"<<endl;//不要忘了这个(其实有没有似乎没有关系)
return 0;
}
//输出啥的......不说 :)

 

大佬勿喷即可qvq

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图