题目如下

继续畅通工程

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 16386    Accepted Submission(s): 7047

Problem Description 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。  

 

Input 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。 当N为0时输入结束。  

 

Output 每个测试用例的输出占一行，输出全省畅通需要的最低成本。  

 

Sample Input 3 1 2 1 0 1 3 2 0 2 3 4 0 3 1 2 1 0 1 3 2 0 2 3 4 1 3 1 2 1 0 1 3 2 1 2 3 4 1 0 Sample Output 3 1 0 使用最小生成树和邻接表，具体思路有注释。   1 #include <iostream> 2 #include <algorithm> 3 #define N 5000 4 5 using std::cin; 6 using std::cout; 7 using std::sort; 8 using std::fill; 9 using std::endl; 10 11 12 typedef struct NODE{ 13 int s;//起点 14 int e;//终点 15 int len;//权值 16 bool is_connected;//是否畅通 17 }node; 18 19 node edge[N]; 20 int parent[N]; 21 bool compare(node a, node b){ 22 //从大到小排列，方便之后查找 23 return b.len > a.len; 24 25 26 } 27 28 int root(int p){ 29 if (parent[p] == -1){ 30 //找到根节点，返回 31 return p; 32 } 33 else{ 34 //递归查找父节点，同时压缩路径 35 //将p节点的父节点更新为父节点的父节点 36 return parent[p] = root(parent[p]); 37 } 38 } 39 40 41 int main(){ 42 int n, m, cost, i, j; 43 //数据量大，换scanf 44 while (scanf("%d", &n) != EOF){ 45 if (n == 0) 46 break; 47 cost = 0; 48 fill(parent, parent + N, -1); 49 m = n*(n - 1) / 2; 50 //read data 51 int start, end, length, conect; 52 for (i = 0; i < m; i++){ 53 scanf("%d %d %d %d", &start, &end, &length, &conect); 54 edge[i].s = start; 55 edge[i].e = end; 56 edge[i].is_connected = conect; 57 if (conect){ 58 edge[i].len = 0; 59 } 60 else{ 61 edge[i].len = length; 62 } 63 } 64 //排序 65 sort(edge, edge + m, compare); 66 //开始按照最短路经生成最小生成树 67 for (i = 0; i < m; i++){ 68 int a, b; 69 //查找父节点 70 //从edge[m-1]开始倒序取数据 71 a = root(edge[i].s); 72 b = root(edge[i].e); 73 //如果没有相连 74 if (a != b){ 75 //将两个集合相连 76 parent[b] = a; 77 //修好了的话就不收钱啦~没修好的才要收钱 78 if (!edge[i].is_connected) 79 cost += edge[i].len; 80 } 81 } 82 printf("%d\n", cost); 83 } 84 return 0; 85 }

 

转载于:https://www.cnblogs.com/JinyaoLi/p/4480728.html