題干：

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 ; }

?

總結

以上是生活随笔為你收集整理的【HDU - 6187】Destroy Walls（思维，最大生成树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。