HDU4313Matrix(用最小生成樹思想，集合劃分)
Matrix
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2598 Accepted Submission(s): 973
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
For 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
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.
解析：要求給出的k個點分開，因為任意兩個集合點只有一條相連，所以我們把這k個點當成k個集合點的根節點，那麼連接這k個集合的邊，它們的權值加起來就是我們要的最小和了。我們將邊按從大到小的順序排好序，然後就是看是否這條邊能夠使得兩個同類的節點連在一起，如果能夠的話，那麼這條邊就是我們要選擇的劃分邊。
#include
#include
using namespace std;
#define LL __int64
const int N = 100005;
struct EDG
{
int u,v;
LL c;
};
int fath[N],typeNode[N],n;
EDG edg[N];
void init()
{
for(int i=0;i<=n;i++)
{
fath[i]=i; typeNode[i]=0;
}
}
int findfath(int x)
{
if(x!=fath[x])
fath[x]=findfath(fath[x]);
return fath[x];
}
LL setfath(int i)
{
int a=findfath(edg[i].u);
int b=findfath(edg[i].v);
if(a==b)
return 0;
if(typeNode[a]&&typeNode[b])
return edg[i].c;
if(typeNode[a])
fath[b]=a;
else
fath[a]=b;
return 0;
}
int cmp(EDG a,EDG b)
{
return a.c>b.c;
}
int main()
{
int t,k,a;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
init();
for(int i=0;i
