杭电acm1863-畅通工程

 

一、Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
 
Input
 
测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。
 
Output
 
对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。
 
Sample Input
 
3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100
 
Sample Output
 
3
 
?

二、Solution

这道题用最小生成树和查并集来解，并查集https://baike.baidu.com/item/%E5%B9%B6%E6%9F%A5%E9%9B%86/9388442?fr=aladdin百度百科中有源代码 使用并查集生成树后若其中有不联通的点那么有两个以上的点父节点为其自身

三、Code

package acm1863;

/**
 * date:2017.12.12
 * author:孟小德
 * function:    杭电acm1863
 *      畅通工程    并查集，最小生成树
 */

import java.util.*;

class Edge implements Comparable<Edge>
{
    public int start,end,cost;

    public Edge(int start,int end,int cost)
    {
        this.start = start;
        this.end = end;
        this.cost = cost;
    }

    public Edge()
    {

    }

    public int compareTo(Edge otherEdge)
    {
        return this.cost - otherEdge.cost;
    }
}

public class Main
{

    public static int NUM_OF_NODE,NUM_OF_EDGE,RESULT;
    public static ArrayList<Edge> LIST_OF_EDGE = new ArrayList<Edge>();
    public static int[] father;

    public static int getParent(int m)
    {
        //  寻找节点的根
        while(father[m] != m)
        {
            m = father[m];
        }

        return m;
    }

    public static int union(int x,int y,int c)
    {
        //  找到两个节点的根若根相同则两节点已联通
        //  否则未联通，将节点链接
        int a = getParent(x);
        int b = getParent(y);

        if (a != b)
        {
            father[a] = b;
            return c;
        }
        return 0;
    }

    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);

        while ((NUM_OF_EDGE = input.nextInt()) != 0)
        {
            NUM_OF_NODE = input.nextInt();
            father = new int[NUM_OF_NODE + 1];
            for (int i=1;i<=NUM_OF_NODE;i++)
            {
                //  初始化根数组，每个节点初始根都是其本身
                father[i] = i;
            }

            for (int i=0;i<NUM_OF_EDGE;i++)
            {
                int s = input.nextInt();
                int e = input.nextInt();
                int c = input.nextInt();

                LIST_OF_EDGE.add(new Edge(s,e,c));
            }
            Collections.sort(LIST_OF_EDGE);//对边进行排序
            RESULT = 0;
            for (int i=0;i<NUM_OF_EDGE;i++)
            {
                int CUR_S = LIST_OF_EDGE.get(i).start;
                int CUR_E = LIST_OF_EDGE.get(i).end;
                int CUR_C = LIST_OF_EDGE.get(i).cost;
                RESULT += union(CUR_S,CUR_E,CUR_C);

            }

            int num = 0;
            for (int i=1;i<=NUM_OF_NODE;i++)
            {
                if (father[i] == i)
                {
                    num++;
                }
            }
            if (num > 1)
            {
                System.out.println("?");
            }
            else
            {
                System.out.println(RESULT);
            }
            LIST_OF_EDGE.clear();
        }

        input.close();
    }
}

最后更新： 2018年12月27日 18:58

原始链接： https://cwhong.top/2018/12/25/程序日记本/杭电acm1863-畅通工程/

cwhong

赏

× Thank you~