HDU-4313 Matrix最小生成ツリー、集合分割

5866 ワード

この問題は、どのように最小の代価を払って1本の木を区別し、後の同類のノードを含まないかを試験することです.
私たちはエッジを大きいものから小さいものに順番に並べて、それからこのエッジが2つの同類のノードをつなぐことができるかどうかを見て、もしできるならば、このエッジは私たちが選択する区分エッジです.まず、フィーチャー値を保持し、セットを調べてタグポイントに拡張します.
コードは次のとおりです.
#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <map>

#include <algorithm>

using namespace std;



int N, M, set[100005], have[100005];



struct Edge

{

    int x, y, fee;

    bool operator < (Edge t) const

    {

        return fee > t.fee;

    }

}e[100005];



int find(int x)

{

    return set[x] = x == set[x] ? x : find(set[x]);

}



void merge(int a, int b)

{

    set[a] = b;

    if (have[a]) {

        have[b] = 1;

    }

}



int main()

{

    int T, a, b, c;

    long long int sum;

    scanf("%d", &T);

    while (T--) {

        sum = 0;

        memset(have, 0, sizeof (have));

        map<int,int>mp;

        scanf("%d %d", &N, &M);

        set[N-1] = N-1;

        for (int i = 0; i < N-1; ++i) {

            scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].fee);

            set[i] = i;

        }

        for (int i = 0; i < M; ++i) {

            scanf("%d", &c); 

            have[c] = 1;

        }

        sort(e, e + N - 1);

        for (int i = 0; i < N-1; ++i) {

            int a = find(e[i].x), b = find(e[i].y);

            if (have[a] && have[b]) {

                sum += e[i].fee;

                continue;

            }

            merge(a, b);

        }

        printf("%I64d
", sum); } return 0; }