首页 > 代码库 > HDU3371 Connect the Cities
HDU3371 Connect the Cities
题目描述：
有n个小岛，其中有的小岛之间没有通路，要修这样一条通路需要花费一定的钱，还有一些小岛之间是有通路的。现在想把所有的岛都连通起来，求最少的花费是多少。
输入：
第一行输入T，代表多少组数据。
第二行输入三个整数n , m , k，分别代表一共有n个小岛，m条路径可供选择，k表示有连通岛的个数。
接下来的m行，每行三个整数p , q , c ，代表建设p到q的通路需要花费的钱为c。
接下的k行，每一行的数据输入如下：先输入Q，代表这个连通分量里面有Q个小岛，然后输入Q个小岛，代表这Q个小岛是连通的。
输出：
输出最少花费为多少，如果无法修建出此路，输出"-1"。
其实这道题属于并查集的入门题目，解法如下：
先用并查集把还在连通的k个分量给合并起来，此时记录好连通分量的个数。然后把Q条路径排一遍序，然后从最小的路径开始枚举，对每一条路径判断起点和终点是否在同一个连通分量内，如果不在的话将这两点合并，连通分量的个数减一，加上修建这条路的花费，如此枚举，知道连通分量的个数为1。如果最后的连通分量大于1，则说明无法连接，输出-1。
可能是解法不太好吧，最后890ms险过，这几天做的并查集都是险过QAQ...
1 #include <iostream> 2 #include <iomanip> 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <algorithm> 6 #include <functional> 7 #include <vector> 8 #include <cmath> 9 #include <string>10 #include <stack> 11 #include <queue>12 using namespace std;13 int k , n , m , father[1005];14 struct P{15 int start , end , cost;16 }p[25000+5]; //路径17 bool cmp(P a , P b)18 {19 return b.cost > a.cost;20 }21 void init()22 {23 for(int i = 1 ; i <= n ; i++) {24 father[i] = i;25 }26 }27 int getf(int v)28 {29 return father[v] = (v == father[v]) ? v : getf(father[v]);30 }31 void merge(int x , int y)32 {33 int a , b;34 a = getf(x);35 b = getf(y);36 if(a != b)37 father[b] = a;38 }39 int main()40 {41 int T , i , j;42 scanf("%d",&T);43 while(T--) 44 {45 scanf("%d %d %d",&n,&m,&k);46 for(i = 1 ; i <= m ; i++)47 scanf("%d %d %d",&p[i].start,&p[i].end,&p[i].cost);48 init();49 for(i = 1 ; i <= k ; i++) {50 int cnt;51 scanf("%d",&cnt);52 int *tmp = new int[cnt];53 for(j = 0 ; j < cnt ; j++) {54 scanf("%d",&tmp[j]);55 if(j != 0)56 merge(tmp[j-1] , tmp[j]);57 }58 delete []tmp;59 }60 sort(p+1 , p+m+1 , cmp);61 int sum = 0; //连通分量的个数62 int ans = 0; 63 for(i = 1 ; i <= n ; i++)64 if(father[i] == i)65 sum++;66 for(i = 1 ; i <= m ; i++) {67 if(sum == 1) //连通分量的个数为1时，说明这时候已经完成 68 break;69 if(getf(p[i].start) != getf(p[i].end)) {70 merge(p[i].start , p[i].end);71 ans += p[i].cost;72 sum--; //连上一条路后连通分量-173 }74 }75 if(sum > 1) {76 printf("-1\n");77 } else {78 printf("%d\n",ans);79 }80 }81 return 0;82 }
HDU3371 Connect the Cities
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。