Kruskal HDOJ 4313 Matrix

题目传送门

题意：如何花最小的代价使得一棵树划分开且不含同类节点

分析：当一条边连接的左右集合同类点小于等于1，那么不用删除，将两个集合合并，要求最小代价，那么贪心思想将权值降序排序，删除后剩下的就是最小值了。树形DP的方法以后再补上

收获：进一步理解Kruskal的算法过程，碰到新的问题要往经典的算法模型上转换

代码：

/************************************************
* Author        :Running_Time
* Created Time  :2015-8-24 10:48:20
* File Name     :D.cpp
 ************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
struct UF	{
	int rt[N], rk[N];
	void init(void)	{
		memset (rt, -1, sizeof (rt));
		memset (rk, 0, sizeof (rk));
	}
	int Find(int x)	{
		return rt[x] == -1 ? x : rt[x] = Find (rt[x]);
	}
	void Union(int x, int y)	{
		x = Find (x), y = Find (y);
		if (x == y)	return ;
		if (rk[x] >= rk[y])	{
			rt[y] = x;	rk[x] += rk[y];
		}
		else	{
			rt[x] = y;	rk[y] += rk[x];
		}
	}
	bool same(int x, int y)	{
		return (Find (x) == Find (y));
	}
}uf;
struct Edge	{
	int u, v, w;
	bool operator < (const Edge &r) const {
		return w > r.w;
	}
};
int n, k;
vector<Edge> G;

int main(void)    {
	int T;	scanf ("%d", &T);
	while (T--)	{
		scanf ("%d%d", &n, &k);
		uf.init ();	G.clear ();
		ll ans = 0;
		for (int u, v, w, i=1; i<n; ++i)	{
			scanf ("%d%d%d", &u, &v, &w);	ans += w;
			G.push_back ((Edge) {u, v, w});
		}
		sort (G.begin (), G.end ());
		for (int x, i=0; i<k; ++i)	{
			scanf ("%d", &x);	uf.rk[x] = 1;
		}
		for (int i=0; i<n-1; ++i)	{
			int u = G[i].u, v = G[i].v, w = G[i].w;
			u = uf.Find (u); v = uf.Find (v);
			if (uf.rk[u] + uf.rk[v] <= 1)	{
				ans -= w;	uf.Union (u, v);
			}
		}
		printf ("%I64d
", ans);
	}

    return 0;
}