暢通工程

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 33566 Accepted Submission(s): 14848

Problem Description

省政府“暢通工程”的目標(biāo)是使全省任何兩個(gè)村莊間都可以實(shí)現(xiàn)公路交通（但不一定有直接的公路相連，只要能間接通過(guò)公路可達(dá)即可）。經(jīng)過(guò)調(diào)查評(píng)估寨腔，得到的統(tǒng)計(jì)表中列出了有可能建設(shè)公路的若干條道路的成本∩艏纾現(xiàn)請(qǐng)你編寫(xiě)程序割按，計(jì)算出全省暢通需要的最低成本两波。
?
Input
?
測(cè)試輸入包含若干測(cè)試用例要拂。每個(gè)測(cè)試用例的第1行給出評(píng)估的道路條數(shù) N巴比、村莊數(shù)目M ( < 100 )术奖；隨后的 N
行對(duì)應(yīng)村莊間道路的成本，每行給出一對(duì)正整數(shù)轻绞，分別是兩個(gè)村莊的編號(hào)采记，以及此兩村莊間道路的成本（也是正整數(shù)）。為簡(jiǎn)單起見(jiàn)政勃，村莊從1到M編號(hào)唧龄。當(dāng)N為0時(shí)，全部輸入結(jié)束奸远，相應(yīng)的結(jié)果不要輸出既棺。
?
Output
?
對(duì)每個(gè)測(cè)試用例，在1行里輸出全省暢通需要的最低成本懒叛。若統(tǒng)計(jì)數(shù)據(jù)不足以保證暢通丸冕，則輸出“?”。
?
Sample Input
?
3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100
?
Sample Output
?
3
?
?

這道題用最小生成樹(shù)和查并集來(lái)解薛窥，并查集https://baike.baidu.com/item/%E5%B9%B6%E6%9F%A5%E9%9B%86/9388442?fr=aladdin百度百科中有源代碼 使用并查集生成樹(shù)后若其中有不聯(lián)通的點(diǎn)那么有兩個(gè)以上的點(diǎn)父節(jié)點(diǎn)為其自身

package acm1863;
 
/**
 * date:2017.12.12
 * author:孟小德
 * function:    杭電acm1863
 *      暢通工程    并查集胖烛，最小生成樹(shù)
 */
 
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)
    {
        //  尋找節(jié)點(diǎn)的根
        while(father[m] != m)
        {
            m = father[m];
        }
 
        return m;
    }
 
    public static int union(int x,int y,int c)
    {
        //  找到兩個(gè)節(jié)點(diǎn)的根若根相同則兩節(jié)點(diǎn)已聯(lián)通
        //  否則未聯(lián)通，將節(jié)點(diǎn)鏈接
        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++)
            {
                //  初始化根數(shù)組诅迷，每個(gè)節(jié)點(diǎn)初始根都是其本身
                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);//對(duì)邊進(jìn)行排序
            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();
    }
}