HDU 4313 Matrix（并查集）

http://acm.hdu.edu.cn/showproblem.php?pid=4313

题意：

给出一棵树，每条边都有权值，其中有几个点是特殊点，现在破坏边还使得这几个特殊点互相不可达，需要使得破坏的边的权值和最小。

思路：
解法很妙！

利用并查集，先将每个点分成一个集合，将边按照降序排序，如果该边两边所在的集合没有特殊点或者只有一边有，那么就可以不用删，用并查集合并。如果两边都有特殊点的话，那就只能删处这条边，因为已经排好序了，所以删的边是尽量最小的。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn = 100005;
 7 typedef long long ll;
 8 
 9 int n, m;
10 int vis[maxn], p[maxn];
11 
12 struct node
13 {
14     int u,v,w;
15     bool operator< (const node& rhs) const
16     {
17         return w > rhs.w;
18     }
19 }a[maxn];
20 
21 int finds(int x)
22 {
23     return x==p[x]?x:p[x]=finds(p[x]);
24 }
25 
26 int main()
27 {
28     //freopen("in.txt","r",stdin);
29     int T;
30     scanf("%d",&T);
31     while(T--)
32     {
33        memset(vis,0,sizeof(vis));
34        scanf("%d%d",&n,&m);
35        for(int i=0;i<n;i++)  p[i] = i;
36        for(int i=0;i<n-1;i++)  scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
37        for(int i=0;i<m;i++)
38        {
39            int x; scanf("%d",&x);
40            vis[x] = 1;
41        }
42        sort(a,a+n-1);
43        ll ans = 0;
44        for(int i=0;i<n-1;i++)
45        {
46            int u = a[i].u;
47            int v = a[i].v;
48            int x = finds(u);
49            int y = finds(v);
50            if(x!=y && (!vis[x]||!vis[y]))
51            {
52                p[x] = y;
53                if(vis[x]||vis[y]) vis[y] = vis[x] = 1;
54            }
55            else ans += a[i].w;
56        }
57        printf("%lld
",ans);
58     }
59     return 0;
60 }