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