首页 > ACM题库 > HDU-杭电 > HDU 4313-Matrix-并查集-[解题报告]HOJ
2015
05-23

HDU 4313-Matrix-并查集-[解题报告]HOJ

Matrix

问题描述 :

Machines have once again attacked the kingdom of Xions. The kingdom of Xions has N cities and N-1 bidirectional roads. The road network is such that there is a
unique path between any pair of cities.

Morpheus has the news that K Machines are planning to destroy the whole kingdom. These Machines are initially living in K different cities of the kingdom and
anytime from now they can plan and launch an attack. So he has asked Neo to destroy some of the roads to disrupt the connection among Machines. i.e after destroying those roads there should not be any path between any two Machines.

Since the attack can be at any time from now, Neo has to do this task as fast as possible. Each road in the kingdom takes certain time to get destroyed and they
can be destroyed only one at a time.

You need to write a program that tells Neo the minimum amount of time he will require to disrupt the connection among machines.

输入:

The first line is an integer T represents there are T test cases. (0<T <=10)
For each test case the first line input contains two, space-separated integers, N and K. Cities are numbered 0 to N-1. Then follow N-1 lines, each containing three, space-separated integers, x y z, which means there is a bidirectional road connecting city x and city y, and to destroy this road it takes z units of time.Then follow K lines each containing an integer. The ith integer is the id of city in which ith Machine is currently located.
2 <= N <= 100,000
2 <= K <= N
1 <= time to destroy a road <= 1000,000

输出:

The first line is an integer T represents there are T test cases. (0<T <=10)
For each test case the first line input contains two, space-separated integers, N and K. Cities are numbered 0 to N-1. Then follow N-1 lines, each containing three, space-separated integers, x y z, which means there is a bidirectional road connecting city x and city y, and to destroy this road it takes z units of time.Then follow K lines each containing an integer. The ith integer is the id of city in which ith Machine is currently located.
2 <= N <= 100,000
2 <= K <= N
1 <= time to destroy a road <= 1000,000

样例输入:

1
5 3
2 1 8
1 0 5
2 4 5
1 3 4
2
4
0

样例输出:

10
Hint
Neo can destroy the road connecting city 2 and city 4 of weight 5 , and the road connecting city 0 and city 1 of weight 5. As only one road can be destroyed at a time, the total minimum time taken is 10 units of time. After destroying these roads none of the Machines can reach other Machine via any path.

题意:给你一个有n(2<=n<=100000)个节点的树,树中每条边都有一个权值。然后再给你k(2<=k<=n)个点,表示这些点上有一个机器人。最后让你删去一些边使任意两个机器人都不能互达,且所删边的权值之和要最小。

思路:我最开始想到的是:

1、将边按权值由小到大排序。

2、计算每条边连接的两个子树中分别有多少个机器人。

3、然后,枚举每条边,如果该条边所连接的两个子树中都有机器人,则将该条边删除。

4、重复步骤2和步骤3,直到枚举完所有的边。

5、所删除的边的权值之和就是要求的结果。

但是,这样做时间复杂度太高,主要是第2步花了太多的时间。后来,发现,完全可以反过来做,思路如下:

1、初始化每个节点为一个集合,并记录每个集合中机器人的数目。

2、将边按权值由大到小排序。

3、枚举每条边,如果该边两端点所在的集合最多只有一个机器人,则合并这两个集合(用并查集),这条边不用删除。否则,这条边要删除。

4、重复步骤3直到枚举完所有边。

5、所删除的边的权值之和就是要求的结果。


代码如下:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

const int maxn = 100010;
int t, n, k;
int mach[maxn], father[maxn];

struct Edge {
	int u, v, c;
}edge;
vector<Edge> vv;

bool cmp(Edge a, Edge b)
{
	return a.c > b.c;
}

void initSet()
{
	for (int i = 0; i < maxn; ++i) {
		father[i] = i;
		mach[i] = 0;
	}
}

int find(int x)
{
	if (x != father[x]) {
		father[x] = find(father[x]);
	}
	return father[x];
}

void merge(int a, int b)
{
	a = find(a);
	b = find(b);
	if (a == b) return ;
	if (a < b) {
		father[b] = a;
		mach[a] += mach[b];
	} else {
		father[a] = b;
		mach[b] += mach[a];
	}
}

int main()
{
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &k);
		vv.clear();
		initSet();
		int u, v, c;
		__int64 ans = 0;
		for (int i = 0; i < n - 1; ++i) {
			scanf("%d%d%d", &u, &v, &c);
			edge.u = u; edge.v = v; edge.c = c;
			vv.push_back(edge);
			ans += c;
		}
		for (int i = 0; i < k; ++i) {
			scanf("%d", &u);
			mach[u] = 1;
		}
		sort(vv.begin(), vv.end(), cmp);
		for (int i = 0; i < n - 1; ++i) {
			u = find(vv[i].u);
			v = find(vv[i].v);
			if (mach[u] + mach[v] <= 1) {
				merge(u, v);
				ans -= vv[i].c;
			}
		}
		printf("%I64d\n", ans);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ahfywff/article/details/7794981