程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 1863 暢通工程

HDU 1863 暢通工程

編輯:關於C++

暢通工程

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

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
?

Source 浙大計算機研究生復試上機考試-2007年
思路:
這道題是一道純模板題,已經給你了點和邊給你連好圖了,所以,你只需要用最小生成樹的方法求解就行了(用到並查集)! 注意:這裡面還有不能夠構成聯通的圖的可能,所以,到最後要用並查集(p[i]==i)的方法判斷有幾個根節點,如果不是一個,那就輸出問好(?),否則輸出結果!
代碼:
#include 
#include 
#include 
using namespace std;
int n,m;
int pre[110];
struct node
{
	int u,v,w;
}p[10100];

int cmp(node a,node b)
{
	return a.w

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved