SGU---462 Electrician 最大生成树

题目链接：

https://cn.vjudge.net/problem/SGU-462

题目大意：

有N条电线需要接入电网，第i条电线计划连接ai和bi两个地点，电线有两个属性：ri（电线稳定度）和ci（电线价值）。电线需要依次接入，如果形成了环，那么环上稳定度最低的电线就会被烧毁。你需要确定一个接入电线的顺序，使得电线总价值最大。

解题思路：

由于形成环，环上的最低稳定度的电线会被烧毁，所以最终的结果一定没有环，也就是一棵以r为关键字的最大生成树（因为最小的r在环上会被烧断，完好无损的就是最大的r），要使得价值最大，那么相同的r就按照价值大的排在前面，排好序求出最大生成树那就是最大价值。

至于连接顺序，只要保持r从小到大或者r从大到小都是可以的。

注意：由于需要将每条边的两个节点进行编号，所以用并查集的时候初始化范围从0到2*n而不是n。因为每条边有两个点。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1e5 + 10;
 5 int n, m;
 6 struct node//存储操作
 7 {
 8     int u, v, id;
 9     ll c, r;
10 }a[maxn];
11 bool cmp1(const node& a, const node& b)
12 {
13     if(a.r == b.r)return a.c > b.c;
14     return a.r > b.r;//最大生成树
15 }
16 bool cmp2(const node& a, const node& b)
17 {
18     if(a.r == b.r)return a.c < b.c;
19     return a.r < b.r;
20 }
21 int fa[maxn];
22 int Find(int x)
23 {
24     return x == fa[x] ? x : fa[x] = Find(fa[x]);
25 }
26 map<int, int>ID;
27 int cnt;
28 int getID(int x)
29 {
30     if(ID[x])return ID[x];
31     return ID[x] = ++cnt;
32 }
33 int main()
34 {
35     while(scanf("%d", &n) != EOF)
36     {
37         ID.clear();
38         cnt = 0;//计数
39         for(int i = 1; i <= n; i++)
40         {
41             scanf("%d%d%lld%lld", &a[i].u, &a[i].v, &a[i].r, &a[i].c);
42             a[i].u = getID(a[i].u);
43             a[i].v = getID(a[i].v);
44             a[i].id = i;
45         }
46         for(int i = 1; i <= cnt; i++)
47             fa[i] = i;
48         sort(a + 1, a + 1 + n, cmp1);
49         ll ans = 0;
50         for(int i = 1; i <= n; i++)
51         {
52             if(Find(a[i].u) != Find(a[i].v))
53             {
54                 ans += a[i].c;
55                 fa[Find(a[i].u)] = Find(a[i].v);
56             }
57         }
58         sort(a + 1, a + 1 + n, cmp2);
59         printf("%lld
%d", ans, a[1].id);
60         for(int i = 2; i <= n; i++)
61             printf(" %d", a[i].id);
62         puts("");
63     }
64     return 0;
65 }