首页 > ACM题库 > HDU-杭电 > HDU 3080-The plan of city rebuild-最小生成树-[解题报告]HOJ
2014
03-01

HDU 3080-The plan of city rebuild-最小生成树-[解题报告]HOJ

The plan of city rebuild

问题描述 :

News comes!~City W will be rebuilt with the expectation to become a center city. There are some villages and roads in the city now, however. In order to make the city better, some new villages should be built and some old ones should be destroyed. Then the officers have to make a new plan, now you , as the designer, have the task to judge if the plan is practical, which means there are roads(direct or indirect) between every two villages(of course the village has not be destroyed), if the plan is available, please output the minimum cost, or output"what a pity!".

输入:

Input contains an integer T in the first line, which means there are T cases, and then T lines follow.
Each case contains three parts. The first part contains two integers l(0<l<100), e1, representing the original number of villages and roads between villages(the range of village is from 0 to l-1), then follows e1 lines, each line contains three integers a, b, c (0<=a, b<l, 0<=c<=1000), a, b indicating the village numbers and c indicating the road cost of village a and village b . The second part first contains an integer n(0<n<100), e2, representing the number of new villages and roads(the range of village is from l to l+n-1), then follows e2 lines, each line contains three integers x, y, z (0<=x, y<l+n, 0<=z<=1000), x, y indicating the village numbers and z indicating the road cost of village x and village y. The third part contains an integer m(0<m<l+n), representing the number of deserted villages, next line comes m integers, p1,p2,…,pm,(0<=p1,p2,…,pm<l+n) indicating the village number.
Pay attention: if one village is deserted, the roads connected are deserted, too.

输出:

Input contains an integer T in the first line, which means there are T cases, and then T lines follow.
Each case contains three parts. The first part contains two integers l(0<l<100), e1, representing the original number of villages and roads between villages(the range of village is from 0 to l-1), then follows e1 lines, each line contains three integers a, b, c (0<=a, b<l, 0<=c<=1000), a, b indicating the village numbers and c indicating the road cost of village a and village b . The second part first contains an integer n(0<n<100), e2, representing the number of new villages and roads(the range of village is from l to l+n-1), then follows e2 lines, each line contains three integers x, y, z (0<=x, y<l+n, 0<=z<=1000), x, y indicating the village numbers and z indicating the road cost of village x and village y. The third part contains an integer m(0<m<l+n), representing the number of deserted villages, next line comes m integers, p1,p2,…,pm,(0<=p1,p2,…,pm<l+n) indicating the village number.
Pay attention: if one village is deserted, the roads connected are deserted, too.

样例输入:

2
4 5
0 1 10
0 2 20
2 3 40
1 3 10
1 2 70
1 1
4 1 60
2
2 3
3 3
0 1 20
2 1 40
2 0 70
2 3
0 3 10
1 4 90
2 4 100
0

样例输出:

70
160

下午看到了这题,第一反应就是MST,既然是MST,可以用Kruskal快速地解决问题,记住在输入所有边之后,删除村庄时把边删除,我的方法是开一个数组ext,ext[i]表示i是否存在,在对边结构体排序的时候,把不存在的边通通放到后面去,这样,当Kruskal过程中,找到一个不存在的边时,就退出,这样会节省比较多的时间。

并查集初始化的时候要全部初始化,以防出现不用的情况。

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int MAX=210;
int n,cnt,ret;
int p[MAX],rank[MAX];
bool ext[MAX];
struct Edge
{
	int from;
	int to;
	int weight;
	
	bool operator<(const Edge& edge) const
	{
		if(ext[from]==false||ext[to]==false)
			return false;
		if(ext[edge.from]==false||ext[edge.to]==false)
			return true;
		return weight<edge.weight;
	}
}edge[MAX*MAX];

void Init()
{
	for(int i=0;i<210;i++)
	{
		p[i]=i;
		rank[i]=0;
	}
}

void Link(int x,int y)
{
	if(rank[x]<rank[y])
		p[x]=y;
	else
	{
		p[y]=x;
		if(rank[x]==rank[y])
			rank[x]++;
	}
}

int Find(int x)
{
	if(p[x]!=x)
		p[x]=Find(p[x]);
		
	return p[x];
}

void Union(int x,int y)
{
	Link(Find(x),Find(y));
}

bool Kruskal()
{
	sort(edge,edge+cnt);
	int done=0;
	
	Init();
	
	for(int i=0;i<cnt&&done<n-1;i++)
	{
		if(ext[edge[i].from]==false||ext[edge[i].to]==false)
			break;
		if(Find(edge[i].from)!=Find(edge[i].to))
		{
			done++;
			ret+=edge[i].weight;
			Union(edge[i].from,edge[i].to);
		}
	}
	
	if(done==n-1)
		return true;
	else
		return false;
}

int main()
{
	int t;
	int x,y,w;
	int nn,ee,m;
	
	scanf("%d",&t);
	while(t--)
	{
		cnt=0;
		ret=0;
		memset(ext,0,sizeof(ext));
		scanf("%d%d",&nn,&ee);
		n=nn;
		for(int i=0;i<nn;i++)
			ext[i]=true;
		for(int i=0;i<ee;i++)
		{
			scanf("%d%d%D",&x,&y,&w);
			edge[cnt].from=x;
			edge[cnt].to=y;
			edge[cnt].weight=w;
			cnt++;
		}
		
		scanf("%d%d",&nn,&ee);
		for(int i=n;i<n+nn;i++)
			ext[i]=true;
		n+=nn;
		for(int i=0;i<ee;i++)
		{
			scanf("%d%d%D",&x,&y,&w);
			edge[cnt].from=x;
			edge[cnt].to=y;
			edge[cnt].weight=w;
			cnt++;
		}
		
		scanf("%d",&m);
		n-=m;
		for(int i=0;i<m;i++)
		{
			scanf("%d",&x);
			ext[x]=false;
		}
		
		if(Kruskal())
			printf("%d/n",ret);
		else
			printf("what a pity!/n");
	}
	
	return 0;
}

 

 

参考:http://blog.csdn.net/lyhypacm/article/details/5776588


  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。