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

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

问题链接:https://vjudge.net/problem/HDU-6187

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

注:写的时候犯了失误,导致用条件编译#define DBG手动调了会儿,结果发现find()函数写错了。。。上面代码如果觉得乱就看下面的,把#define DBG相关部分全部删除后的:

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