CF-1023F.Mobile Phone Network(并查集縮點)

題目鏈接

題意

你手里有K條邊還沒有分配權值,已經存在M條邊帶權值,如何給你手中的邊分配權值,使得K條邊都在最后的最小生成樹中且最后權值和最大.

思路

首先將K條邊權值設為0求一個最小生成樹.

對于剩下的邊,當且僅當加入這條邊形成環上的最小權值為這條邊的權值時,才能保證K條邊不會被替換同時權值盡可能的大.

對剩下的邊,優先考慮最小的邊,如果最小的邊都已經滿足,那么大的邊也能滿足.所以對已經確定的邊可以用并查集縮到一起

最后判斷K條邊是不是都已經確定

#include <bits/stdc++.h> const int maxn = 5e5 + 5; using namespace std; vector<tuple<int,int,int> >edge; vector<pair<int,int> > g[maxn]; int pre[maxn], fa_e[maxn], fa_v[maxn], dep[maxn]; int ans[maxn]; int n, m, k; int find(int x) {return (x == pre[x]) ? x : pre[x] = find(pre[x]); } void kruskal() {for (int i = 0; i <= n; ++i) pre[i] = i;for (int i = 0; i < (int)edge.size(); ++i) {int u, v, c;tie(u, v, c) = edge[i];int fu = find(u);int fv = find(v);if (fu == fv) continue;pre[fv] = fu;int id = i < k ? i+1 : k+1; // id = i+1 會超內存g[u].push_back(make_pair(v, id));g[v].push_back(make_pair(u, id));} } void dfs(int u) {for (auto it : g[u]) {int v, id;tie(v, id) = it;if (fa_v[v]) continue;fa_v[v] = u;fa_e[v] = id;dep[v] = dep[u] + 1;dfs(v);} } int main() {scanf("%d %d %d", &n, &k, &m);for (int i = 0; i < k; ++i) {int u, v;scanf("%d %d", &u, &v);edge.push_back(make_tuple(u, v, 0));}for (int i = 0; i < m; ++i) {int u, v, c;scanf("%d %d %d", &u, &v, &c);edge.push_back(make_tuple(u, v, c));}kruskal();fa_v[1] = 1;fa_e[1] = 1;dfs(1);fill(ans, ans+n+1, -1);for (int i = 1; i <= n; ++i) pre[i] = i;for (int i = k; i < (int)edge.size(); ++i) {int u, v, c;tie(u, v, c) = edge[i];while (true) {u = find(u);v = find(v);if (u == v) break;if (dep[u] < dep[v]) swap(u, v);ans[fa_e[u]] = c;pre[u] = fa_v[u];}} long long Ans = 0;for (int i = 1; i <= k; ++i) {if (ans[i] == -1) {Ans = -1;break;} Ans += ans[i];}printf("%lld\n", Ans);return 0; }

總結

以上是生活随笔為你收集整理的CF-1023F.Mobile Phone Network(并查集缩点)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。