首页 > ACM题库 > HDU-杭电 > HDU 3371-Connect the Cities-最小生成树-[解题报告]HOJ
2014
03-16

HDU 3371-Connect the Cities-最小生成树-[解题报告]HOJ

Connect the Cities

问题描述 :

In 2100, since the sea level rise, most of the cities disappear. Though some survived cities are still connected with others, but most of them become disconnected. The government wants to build some roads to connect all of these cities again, but they don’t want to take too much money.  

输入:

The first line contains the number of test cases.
Each test case starts with three integers: n, m and k. n (3 <= n <=500) stands for the number of survived cities, m (0 <= m <= 25000) stands for the number of roads you can choose to connect the cities and k (0 <= k <= 100) stands for the number of still connected cities.
To make it easy, the cities are signed from 1 to n.
Then follow m lines, each contains three integers p, q and c (0 <= c <= 1000), means it takes c to connect p and q.
Then follow k lines, each line starts with an integer t (2 <= t <= n) stands for the number of this connected cities. Then t integers follow stands for the id of these cities.

输出:

The first line contains the number of test cases.
Each test case starts with three integers: n, m and k. n (3 <= n <=500) stands for the number of survived cities, m (0 <= m <= 25000) stands for the number of roads you can choose to connect the cities and k (0 <= k <= 100) stands for the number of still connected cities.
To make it easy, the cities are signed from 1 to n.
Then follow m lines, each contains three integers p, q and c (0 <= c <= 1000), means it takes c to connect p and q.
Then follow k lines, each line starts with an integer t (2 <= t <= n) stands for the number of this connected cities. Then t integers follow stands for the id of these cities.

样例输入:

1
6 4 3
1 4 2
2 6 1
2 3 5
3 4 33
2 1 2
2 1 3
3 4 5 6

样例输出:

1

HDU_STEPS 6.1 最小生成树

 

6.1.1 HDU 1102 Constructing Roads 裸的最小生成树

6.1.2 HDU 1162 Eddy’s picture 最小生成树,每两点直接连线建图

6.1.3 HDU 1232 畅通工程 用并查集将图分块,然后修N-1条路即可

6.1.4 HDU 1233 还是畅通工程 还是最小生成树

6.1.5 HDU 1879 继续畅通工程 在已生成部分图的情况下生成最小生成树,输入的时候用并查集合并已经连接的端点

6.1.6 HDU 1301 Jungle Roads 将字母转换成数字建图即可,还是最小生成树

6.1.7 HDU 3371 Connect the Cities

先用并查集将地图分块,连接N块要N-1条路.然后用克鲁斯卡耳生成最小生成树,每合并一次计数加1,说明修了1条路,如果最后修的路的条数<n-1,说明不连通

#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
struct edge{
	int u,v,w;
	bool operator <(const edge& ee)const{return w<ee.w;} 
}e[25005];
int p[505],cas,n,m,k,hash[505];
int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
int main(){
	scanf("%d",&cas); 
	while(cas--){
		scanf("%d%d%d",&n,&m,&k);
		
		for(int i=1;i<=n;i++)p[i]=i;
		memset(hash,0,sizeof hash);
		
		for(int i=0;i<m;i++)
			scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
		for(int i=0;i<k;i++){
			int t,st,en;
			scanf("%d%d",&t,&st);t--;
			while(t--){
				scanf("%d",&en);
				p[find(st)]=find(en);	
			}	
		}
		int tot=0,cnt=0;
		for(int i=1;i<=n;i++)
			if(!hash[find(i)])tot++,hash[find(i)]=1;
		tot--;//需要增加的边的条数 
			 
		sort(e,e+m);
		
		int res=0;
		for(int i=0;i<m;i++){
			int x=find(e[i].u),y=find(e[i].v);	
			if(x==y)continue;
			res+=e[i].w;
			p[x]=y;
			cnt++;
			if(cnt==tot)break;//已经连通了 
		}
		
		if(cnt<tot)printf("-1\n");
		else printf("%d\n",res);
	}
}

6.1.8 HDU 3367 Pseudoforest

求一个最大生成森林,每个连通块里至多只有一个环

先贪心按从大到小对边排序。如果并入的两个点在一个集合中并且这个集合没有环,就并入这个点并将这个集合标记为有环;如果两个点在不同集合且都有环,就不能加这条边;如果只有一个有环,则并入有环的那部分

#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAXN 10001
using namespace std;
struct edge{
	int u,v,w,us;
	edge(){};
	edge(int a,int b,int c){u=a,v=b,w=c,us=0;}
	bool operator<(const edge& e)const{return w>e.w;}	
}e[MAXN*10];
int p[MAXN],n,m,cir[MAXN]; 
int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
int main(){
	while(scanf("%d%d",&n,&m),n||m){
		for(int i=0;i<n;i++)p[i]=i;
		memset(cir,0,sizeof cir);
		
		for(int i=0;i<m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
		
		sort(e,e+m);
		int res=0;
		for(int i=0;i<m;i++){
			int x=find(e[i].u),y=find(e[i].v);
			if(x==y&&cir[x]==0){//如果两点在同一个块且无环 
				cir[x]=1;
				res+=e[i].w;
			}
			if(cir[x]&&cir[y])continue;//如果都有环就不能连了 
			if(cir[x])p[y]=x;//如果x有环,将y并入x中 
			else p[x]=y;	//否则将x并入y中 
			res+=e[i].w;			
		}

		printf("%d\n",res);
	}
}

参考:http://blog.csdn.net/swm8023/article/details/6890728