【HDU - 6187】Destroy Walls（思维，最大生成树）

题干：

Long times ago, there are beautiful historic walls in the city. These walls divide the city into many parts of area. 

Since it was not convenient, the new king wants to destroy some of these walls, so he can arrive anywhere from his castle. We assume that his castle locates at (0.6∗2–√,0.6∗3–√)(0.6∗2,0.6∗3). 

There are nn towers in the city, which numbered from 1 to n. The ith's location is (xi,yi)(xi,yi). Also, there are m walls connecting the towers. Specifically, the ith wall connects the tower uiui and the tower vivi(including the endpoint). The cost of destroying the ith wall is wiwi. 

Now the king asks you to help him to divide the city. Firstly, the king wants to destroy as less walls as possible, and in addition, he wants to make the cost least.

The walls only intersect at the endpoint. It is guaranteed that no walls connects the same tower and no 2 walls connects the same pair of towers. Thait is to say, the given graph formed by the walls and towers doesn't contain any multiple edges or self-loops. 

Initially, you should tell the king how many walls he should destroy at least to achieve his goal, and the minimal cost under this condition. 

Input

There are several test cases. 

For each test case: 

The first line contains 2 integer n, m. 

Then next n lines describe the coordinates of the points. 

Each line contains 2 integers xi,yixi,yi. 

Then m lines follow, the ith line contains 3 integers ui,vi,wiui,vi,wi 

|xi|,|yi|≤105|xi|,|yi|≤105 

3≤n≤100000,1≤m≤2000003≤n≤100000,1≤m≤200000 

1≤ui,vi≤n,ui≠vi,0≤wi≤100001≤ui,vi≤n,ui≠vi,0≤wi≤10000 

Output

For each test case outout one line with 2 integers sperate by a space, indicate how many walls the king should destroy at least to achieve his goal, and the minimal cost under this condition. 

Sample Input

4 4
-1 -1
-1 1
1 1
1 -1
1 2 1
2 3 2
3 4 1
4 1 2

Sample Output

1 1

题目大意：

　　有一个V座塔（告诉你每座塔的x,y坐标）M条边（链接两个塔）的带边权无向平面图，有一个人在一个区域，坐标是，要拆一些墙使得他可以到达任意一个区域，问最小花费。

解题报告：

   不难想到，其实可以将每一个联通区域看成一个点，将一堵墙看做两个点之间的边被切断了，边权就是对应的wi，也就是说你需要让他们连通起来，即让他变成一个连通图，这样我们只需要构造一棵MST就好了。但是对于如何把整个图划分成点，这就比较麻烦，我们可以换个角度分析，其实就是直接考虑删边。其实删边的过程就是破环的过程，也就是让最后的图中没有一个环，所以我们考虑做法，对每一个块，求个最大生成树就好了。那么怎么统计块数呢？其实也不用这么麻烦，直接建一个虚点，对每个点都连边就好了，然后直接求最大生成树，最后用总边权减去最大生成树的权值，剩下的一定就是都要删去的边。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 5e5 + 5;
int x[MAX],y[MAX];
struct Node {
	int u,v;
	ll w;
} e[MAX];
int tot,n,m;
bool cmp(Node a,Node b) {
	return a.w > b.w;
}
int f[MAX];
int getf(int v) {
	return f[v] == v ? v : f[v] = getf(f[v]);
}
int merge(int u,int v) {
	int t1 = getf(u);
	int t2 = getf(v);
	f[t2] = t1;
}
int main()
{
	int u,v;
	ll w;
	while(~scanf("%d%d",&n,&m)) {
		tot=0;
		for(int i = 1; i<=n+1; i++) f[i] = i;
		for(int i = 1; i<=n; i++) scanf("%d%d",x+i,y+i);
		ll ans2 = 0;
		for(int i = 1; i<=m; i++) {
			scanf("%d%d%lld",&u,&v,&w);
			e[i].u = u,e[i].v = v;e[i].w = w;
			ans2 += w;
		}
		tot=m;
		for(int i = 1; i<=n; i++) {
			e[++tot].u = i;
			e[tot].v = n+1;
			e[tot].w = -123123;
		}
		sort(e+1,e+m+1,cmp);
		ll ans = 0,ee=0;
		for(int i = 1; i<=tot; i++) {
			int u = e[i].u;
			int v = e[i].v;
			if(getf(u) == getf(v)) continue;
			if(e[i].w >= 0) {
				ans += e[i].w;
				ee++;
			}		
			merge(u,v);
		}
		printf("%lld %lld\n",m-ee,ans2-ans);
	}
	return 0 ;
}