## 【HDU-6187】Destroy Walls【最大生成树】

【HDU-6187】Destroy Walls【最大生成树】

Solution:

```#include <iostream>
#include <algorithm>
// #define DBG

using namespace std;

const int LIM = 1e5 + 10;
struct Edge{
int x, y, w;
bool operator < (const Edge &e) const { return w > e.w; }
} edges[LIM * 2];
int parent[LIM];

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

bool Union(int x, int y) {
int xpos = find(x);
int ypos = find(y);
if (xpos == ypos) {
return false;
} else {
parent[ypos] = parent[xpos];
return true;
}
}

int main(void) {
int n, m;
while (~scanf("%d%d", &n, &m)) {
int sum = 0, cnt = 0, rest = 0;
for (int i = 1; i <= n; i++) {
scanf("%*d%*d");
parent[i] = i;
}
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].w);
sum += edges[i].w;
}
sort(edges, edges + m);
#ifdef DBG
printf("Sorting...Done!\n");
for (int i = 0; i < m; i++) {
printf("edges[%d]: x = %d, y = %d, w = %d\n", i, edges[i].x, edges[i].y, edges[i].w);
}
printf("Show the edges...Done!\n");
#endif
for (int i = 0; i < m; i++) {
if (Union(edges[i].x, edges[i].y)) cnt++, rest += edges[i].w;
#ifdef DBG
printf("now cnt = %d, rest = %d, sum = %d\n", cnt, rest, sum);
printf("The parent[]:\n");
for (int i = 1; i <= n; i++)
printf("\tparent[%d] : %d\n", i, parent[i]);
printf("Done...\n");
#endif
}
printf("%d %d\n", m - cnt, sum - rest);
}
return 0;
}
```

```#include <iostream>
#include <algorithm>
using namespace std;

const int LIM = 1e5 + 10;
struct Edge{
int x, y, w;
bool operator < (const Edge &e) const { return w > e.w; }
} edges[LIM * 2];
int parent[LIM];

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

bool Union(int x, int y) {
int xpos = find(x);
int ypos = find(y);
if (xpos == ypos) {
return false;
} else {
parent[ypos] = parent[xpos];
return true;
}
}

int main(void) {
int n, m;
while (~scanf("%d%d", &n, &m)) {
int sum = 0, cnt = 0, rest = 0;
for (int i = 1; i <= n; i++) {
scanf("%*d%*d");
parent[i] = i;
}
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].w);
sum += edges[i].w;
}
sort(edges, edges + m);
for (int i = 0; i < m; i++) {
if (Union(edges[i].x, edges[i].y)) cnt++, rest += edges[i].w;
}
printf("%d %d\n", m - cnt, sum - rest);
}
return 0;
}
```