Kruskal: Matrix
Matrix
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 441 Accepted Submission(s): 162
Problem Description
Machines have once again attacked the kingdom of Xions. The kingdom of Xions has N cities and N-1 bidirectional roads. The road network is such that there is a
unique path between any pair of cities.
Morpheus has the news that K Machines are planning to destroy the whole kingdom. These Machines are initially living in K different cities of the kingdom and
anytime from now they can plan and launch an attack. So he has asked Neo to destroy some of the roads to disrupt the connection among Machines. i.e after destroying those roads there should not be any path between any two Machines.
Since the attack can be at any time from now, Neo has to do this task as fast as possible. Each road in the kingdom takes certain time to get destroyed and they
can be destroyed only one at a time.
You need to write a program that tells Neo the minimum amount of time he will require to disrupt the connection among machines.
Input
The first line is an integer T represents there are T test cases. (0For each test case the first line input contains two, space-separated integers, N and K. Cities are numbered 0 to N-1. Then follow N-1 lines, each containing three, space-separated integers, x y z, which means there is a bidirectional road connecting city x and city y, and to destroy this road it takes z units of time.Then follow K lines each containing an integer. The ith integer is the id of city in which ith Machine is currently located.
2 <= N <= 100,000
2 <= K <= N
1 <= time to destroy a road <= 1000,000
Output
For each test case print the minimum time required to disrupt the connection among Machines.
Sample Input
Sample Output
杭電のホームページでは貪欲アルゴリズムを使うと言っています:kruskalの最小生成木の過程に似ていますが、ここでは重み値を大きくから小さく並べながら、辺を加えるたびに2つの危険な点を連通させるかどうかを判断します.そうすれば、この辺は削除される必要があります.そうしないと、木に追加されます.
さらに注意したいのは、
私たちは1つの都市がmachineがあれば邪悪で、最初はそのk都市だけが邪悪だと言った.
また、1つのエッジが追加されて2つの危険点が連通するかどうかを判断する際には、その2つの端点の祖先が邪悪であるかどうかを判断する必要があり、2つの同時に邪悪でなければ、このエッジが追加できることに注意してください.
加えられたエッジの2つの端点の祖先が少なくとも1つが邪悪であれば、この2つの祖先は邪悪にならなければならない.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 441 Accepted Submission(s): 162
Problem Description
Machines have once again attacked the kingdom of Xions. The kingdom of Xions has N cities and N-1 bidirectional roads. The road network is such that there is a
unique path between any pair of cities.
Morpheus has the news that K Machines are planning to destroy the whole kingdom. These Machines are initially living in K different cities of the kingdom and
anytime from now they can plan and launch an attack. So he has asked Neo to destroy some of the roads to disrupt the connection among Machines. i.e after destroying those roads there should not be any path between any two Machines.
Since the attack can be at any time from now, Neo has to do this task as fast as possible. Each road in the kingdom takes certain time to get destroyed and they
can be destroyed only one at a time.
You need to write a program that tells Neo the minimum amount of time he will require to disrupt the connection among machines.
Input
The first line is an integer T represents there are T test cases. (0
2 <= N <= 100,000
2 <= K <= N
1 <= time to destroy a road <= 1000,000
Output
For each test case print the minimum time required to disrupt the connection among Machines.
Sample Input
1
5 3
2 1 8
1 0 5
2 4 5
1 3 4
2
4
0
Sample Output
10
Hint
Neo can destroy the road connecting city 2 and city 4 of weight 5 , and the road connecting city 0 and city 1 of weight 5. As only one road can be destroyed at a time, the total minimum time taken is 10 units of time. After destroying these roads none of the Machines can reach other Machine via any path.
杭電のホームページでは貪欲アルゴリズムを使うと言っています:kruskalの最小生成木の過程に似ていますが、ここでは重み値を大きくから小さく並べながら、辺を加えるたびに2つの危険な点を連通させるかどうかを判断します.そうすれば、この辺は削除される必要があります.そうしないと、木に追加されます.
さらに注意したいのは、
私たちは1つの都市がmachineがあれば邪悪で、最初はそのk都市だけが邪悪だと言った.
また、1つのエッジが追加されて2つの危険点が連通するかどうかを判断する際には、その2つの端点の祖先が邪悪であるかどうかを判断する必要があり、2つの同時に邪悪でなければ、このエッジが追加できることに注意してください.
加えられたエッジの2つの端点の祖先が少なくとも1つが邪悪であれば、この2つの祖先は邪悪にならなければならない.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
#define M 100010;
int n, k;
int flag[100010];
int p[100010];
long long ans;
long long sum;
int flag1, flag2;
struct edge{
int u;
int v;
long long w;
}e[100010];
int find(int x){
return p[x] == x ? x : p[x] = find(p[x]);
}
int cmp(edge a, edge b){ //
return a.w > b.w;
}
int Kruscal(){
int i;
ans = 0;
sort(e, e+n-1, cmp);
for(i = 0; i < n-1; i ++){
int x = find(e[i].u);
int y = find(e[i].v);
if(x != y && !(flag[x] && flag[y])){
if(flag[x] || flag[y]){
flag[x] = 1;
flag[y] = 1;
}
ans += e[i].w;
p[x] = y;
}
}
return ans;
}
int main(){
int t;
int i, tmp;
cin >> t;
while(t --){
sum = 0;
scanf("%d %d", &n, &k);//k k-1 ， n-k
//cout << "n=" << n << endl;
for(i = 0; i < n-1; i ++){
//cout << "i=" << i << endl;
scanf("%d %d %I64d",&e[i].u, &e[i].v, &e[i].w);
sum += e[i].w;
}
for(i = 0; i < n; i ++){
flag[i] = 0;
p[i] = i;
}
for(i = 0; i < k; i ++){
scanf("%d", &tmp);
flag[tmp] = 1;
}
Kruscal();
cout << sum - ans << endl;
}
return 0;
}
/*
2
5 3
2 1 8
1 0 5
2 4 5
1 3 4
2
4
0
5 3
2 1 8
1 0 5
2 4 5
1 3 4
2
4
0
*/