本文主要是介绍Benelux Algorithm Programming Contest 2020部分题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
牛客题目链接
F-Generator Grid
这题我在看了解析后突然理解了它的做法，用最小生成树的算法。
那么如何处理发电站呢？可以将发电站看做额外的节点，将发电站与可以建的地方相连。也就是点权转边权。
以示例1为例子，发电站就是额外的节点n+1=4，建立发电站的费用就是边权。一共要连n-1也就是3条边。
#include <bits/stdc++.h>
using namespace std;struct side
{int x, y, l;
} s[200005];
int fa[200005];bool cmp(side a, side b)
{return a.l < b.l;
}
//查找集合，同时实现路径压缩
int find(int n)
{if (fa[n] == n)return n;return fa[n] = find(fa[n]);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int n, m, x, l, cnt = 0;long long ans = 0;cin >> n >> m;while (m--) //输入发电站{cin >> x >> l;s[++cnt] = {x, n + 1, l}; //发电站作为n之外的结点}for (int i = 1; i < n; i++)//输入线路{fa[i] = i;cin >> l;s[++cnt] = {i, i + 1, l};}cin >> l;s[++cnt] = {n, 1, l}; //最后一个与结点1相连fa[n] = n;fa[n + 1] = n + 1;sort(s + 1, s + cnt + 1, cmp); //排序for (int i = 1; i <= cnt; i++){int f1 = find(s[i].x), f2 = find(s[i].y);if (f1 == f2)continue;fa[f1] = fa[f2];ans += s[i].l;}cout << ans;return 0;
}这篇关于Benelux Algorithm Programming Contest 2020部分题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
