【图论】1 （最小生成树&捏造点思想）C.戴森球筹划 题解 ...

一. 题目

题目形貌

输入输出格式

样例

样例1

样例2 & 样例解释

数据范围

二. 思路

对于前20%数据 解法

由于保证了                                              x                            i                                  =                         1                              x_i = 1                  xi​=1，也就是说这些点都在                                    x                         =                         1                              x = 1                  x=1 这条直线上。
那么最优解肯定是在                                              c                            i                                       c_i                  ci​ 最小的点上建发电站，然后把这些点之间全部联通即可。
即终极答案                                         a                            n                            s                            =                                                   min                                  ⁡                                                      1                                  ≤                                  i                                  ≤                                  n                                                            c                               i                                      +                                                   max                                  ⁡                                                      1                                  ≤                                  i                                  ≤                                  n                                                            y                               i                                      −                                                   min                                  ⁡                                                      1                                  ≤                                  i                                  ≤                                  n                                                            y                               i                                            ans = \min_{1 \leq i \leq n}c_i + \max_{1 \leq i \leq n}y_i - \min_{1 \leq i \leq n} y_i                     ans=1≤i≤nmin​ci​+1≤i≤nmax​yi​−1≤i≤nmin​yi​
可见，我们要枚举                                    1                              1                  1 到                                    n                              n                  n ，所以时间复杂度为                                    O                         (                         n                         )                              O(n)                  O(n) 。
对于前70%数据 解法

思路分析

由于50%的数据没有什么特别的地方（至少作者没有想到），所以直接从70%的数据入手。
思索：                                             k                            i                                  =                         1                              k_i = 1                  ki​=1 ，也就是点之间的连线每条边的单元花费为                                    1                         +                         1                         =                         2                              1+1=2                  1+1=2 ，而                                    1                                   0                            8                                  ≤                                   c                            i                                  ≤                         1                                   0                            9                                       10^8 \leq c_i \leq 10^9                  108≤ci​≤109 很大，并且在                                    n                         ≤                         2000                              n \leq 2000                  n≤2000 的情况下，我们发现连线的花费往往小于构建发电站的花费。所以容易得出贪心策略：在                                                    c                               i                                            c_i                     ci​ 最小的点建发电站，其他点都与这个点联通。
这个问题就等价于要把图上的每一个点都联通，并且花费最小。
先思量怎样联通每一个点：构建一棵树，共有                                    n                              n                  n 个点和                                    n                         −                         1                              n-1                  n−1 条边。
其次要让花费小：这不就是最小生成树吗？！
具体实现

我们先把                                    n                              n                  n 个点之间两两连线，每条边的权值为该边的花费，构建一个完全图，然后对这张图 跑Kruskal或Prim（最小生成树） 即可。
对于100%数据 解法

发现100%的数据与70%的数据对比，                                             k                            i                                       k_i                  ki​ 与                                              c                            i                                       c_i                  ci​ 的取值范围更广泛，所以不一定只有一个发电站是最优解。
那么按照70%数据的思路，我们对于每一个发电站，都会构建出一棵最小生成树，但一棵不一定涵盖全部点。即这张图变成了一个最小生成树组成的森林。
这样的话，我们没法枚举每个发电站再构建最小生成树。能不能把这些树合在一起呢？
这里，我们引入 “捏造点思想”，也叫做 “超等零点” 。也就是新增0号（或不在范围内的）点，并把它向其他点都连一条边，边的权值为在与其相连的点构建发电站的花费。
这样，我们就可以对这个图跑最小生成树即可。由于最小生成树一定会连向捏造点，所以至少会构建一个发电站，思路可行。
三. 代码实现

20pts 解法

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N = 2055;
4. long long id,n,k[N],x[N],y[N],maxx,minn=1e17,ress=1e17;
5. long long c[N],f[N],res = 1e17,ans = 0,cnt;
6. struct node
7. {
8.         long long u,v,w;
9. }a[N*N*2];
10. int main()
11. {
12.         freopen("electricity.in","r",stdin);
13.         freopen("electricity.out","w",stdout);
14.         cin >> id;
15.         cin >> n;
16.         for (int i=1;i<=n;i++)
17.         {
18.                 scanf("%lld%lld",&x[i],&y[i]);
19.         }
20.         for (int i=1;i<=n;i++)
21.         {
22.                 scanf("%lld",&c[i]);
23.         }
24.         for (int i=1;i<=n;i++)
25.         {
26.                 scanf("%lld",&k[i]);
27.         }
28.        
29.         if (1 <= id && id <= 4)
30.         {
31.                 for (int i=1;i<=n;i++)
32.                 {
33.                         maxx = max(maxx,y[i]);
34.                         minn = min(minn,y[i]);
35.                         ress = min(ress,c[i]);
36.                 }
37.                 cout<<(maxx-minn)*2+ress;
38.                 return 0;
39.         }
40.         return 0;
41. }

复制代码

70pts 解法

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N = 2005;
4. long long id,n,k[N],x[N],y[N],maxx,minn=1e17,ress=1e17;
5. long long c[N],f[N],res = 1e17,ans = 1e17,cnt;
6. struct node
7. {
8.         long long u,v,w;
9. }a[N*N];
10. long long zabs(long long s)
11. {
12.         if (s > 0) return s;
13.         return -s;
14. }
15. long long dis(long long a,long long b)
16. {
17.         return zabs(x[a]-x[b])+zabs(y[a]-y[b]);
18. }
19. void add(long long h,long long b,long long c)
20. {
21.         a[++cnt].u = h;
22.         a[cnt].v = b;
23.         a[cnt].w = c;
24. }
25. bool cmp(node x,node y)
26. {
27.         return x.w < y.w;
28. }
29. long long fnd(int x)
30. {
31.         if (x == f[x]) return x;
32.         return f[x] = fnd(f[x]);
33. }
34. int main()
35. {
36.         freopen("electricity.in","r",stdin);
37.         freopen("electricity.out","w",stdout);
38.         cin >> id;
39.         cin >> n;
40.         for (int i=1;i<=n;i++)
41.         {
42.                 scanf("%lld%lld",&x[i],&y[i]);
43.         }
44.         for (int i=1;i<=n;i++)
45.         {
46.                 scanf("%lld",&c[i]);
47.         }
48.         for (int i=1;i<=n;i++)
49.         {
50.                 scanf("%lld",&k[i]);
51.         }
52.         ans = 1e17;
53.         for (int i=1;i<=n;i++)
54.         {
55.                 ans = mins(ans,c[i]);
56.         }
57.         for (int i=1;i<n;i++)
58.         {
59.                 for (int j=i+1;j<=n;j++)
60.                 {
61.                         add(j,i,dis(i,j)*(k[i]+k[j]));
62.                         add(i,j,dis(i,j)*(k[i]+k[j]));
63.                 }
64.         }
65.         sort(a+1,a+cnt+1,cmp);
66.         long long tot = 0;
67.         for (int j=1;j<=n;j++)
68.         {
69.                 f[j] = j;
70.         }
71.         for (int j=1;j<=cnt;j++)
72.         {
73.                 long long p1 = fnd(f[a[j].u]);
74.                 long long p2 = fnd(f[a[j].v]);
75.                 if (f[p1] == f[p2]) continue;
76.                 f[p1] = fnd(f[p2]);
77.                 ans += a[j].w;
78.                 tot++;
79.                 if (tot+1 == n) break;
80.         }
81.         cout<<ans;
82.         return 0;
83. }

复制代码

100pts 解法

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N = 2055;
4. long long id,n,k[N],x[N],y[N],maxx,minn=1e17,ress=1e17;
5. long long c[N],f[N],res = 1e17,ans = 0,cnt;
6. struct node
7. {
8.         long long u,v,w;
9. }a[N*N*2];
10. long long zabs(long long s)
11. {
12.         if (s > 0) return s;
13.         return -s;
14. }
15. long long dis(long long a,long long b)
16. {
17.         return zabs(x[a]-x[b])+zabs(y[a]-y[b]);
18. }
19. void add(long long h,long long b,long long c)
20. {
21.         a[++cnt].u = h;
22.         a[cnt].v = b;
23.         a[cnt].w = c;
24. }
25. bool cmp(node x,node y)
26. {
27.         return x.w < y.w;
28. }
29. long long fnd(int x)
30. {
31.         if (x == f[x]) return x;
32.         return f[x] = fnd(f[x]);
33. }
34. int main()
35. {
36.         freopen("electricity.in","r",stdin);
37.         freopen("electricity.out","w",stdout);
38.         cin >> id;
39.         cin >> n;
40.         for (int i=1;i<=n;i++)
41.         {
42.                 scanf("%lld%lld",&x[i],&y[i]);
43.         }
44.         for (int i=1;i<=n;i++)
45.         {
46.                 scanf("%lld",&c[i]);
47.         }
48.         for (int i=1;i<=n;i++)
49.         {
50.                 scanf("%lld",&k[i]);
51.         }
52.         ans = 0;
53.         //构图
54.         for (int i=1;i<n;i++)
55.         {
56.                 for (int j=i+1;j<=n;j++)
57.                 {
58.                         add(j,i,dis(i,j)*(k[i]+k[j]));
59.                         add(i,j,dis(i,j)*(k[i]+k[j]));
60.                 }
61.         }
62.         //虚拟点构建
63.         for (int i=1;i<=n;i++)
64.         {
65.                 add(n+1,i,c[i]);
66.                 add(i,n+1,c[i]);
67.         }
68.         sort(a+1,a+cnt+1,cmp);
69.         long long tot = 0;
70.         for (int j=1;j<=n+1;j++)
71.         {
72.                 f[j] = j;
73.         }
74.         //Kruskal最小生成树
75.         for (int j=1;j<=cnt;j++)
76.         {
77.                 long long p1 = fnd(f[a[j].u]);
78.                 long long p2 = fnd(f[a[j].v]);
79.                 if (f[p1] == f[p2]) continue;
80.                 f[p1] = fnd(f[p2]);
81.                 ans += a[j].w;
82.                 tot++;
83.                 if (tot == n) break;
84.         }
85.         cout<<ans;
86.         return 0;
87. }

复制代码

四. 总结

这道图论题在CSP-J模拟赛放了T3，感觉略难（最小生成树和捏造点思想略有超纲），但不引进“捏造点思想”的70分给的很足。总体来说是一道练习最小生成树和捏造点思想的好题。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。