杭电多校第二场 1001 Total Eclipse 题解

题目大意

给你一个n个点m边的双向图，你可以进行一个操作，选择一个数字k，选择k个互相联通的点，使这些点的权值减一，问最少需要多少次操作。

解题思路

刚开始打的时候，看到这个题过得还挺多的，又过的快。

以为是签到题。。

结果完全没思路。。

杭电多校还是难啊，补题都很困难。

对于任何一个图来说，最优解肯定是优先最大连通块，减去连通块中最小的值，然后对于分裂之后的所有连通块再进行相同的操作。

所以我们可以倒过来看，选择权值由大到小的点，每个点的贡献为前一个点的的权值减去现在的点的权值乘以目前连通块的数量，就是将大的点减小成目前点所需要的次数。

在从第二个点开始枚举的过程中，需要枚举这个点的边，如果连接的是以前被标记的点，就可以判断这两点是不是属于同一个连通块的，以此来控制连通块的数量。

最后还需要加上最后一个点的权值乘以连通块的数量。

说实话，这个题目还挺难想的。。。

不愧是杭电多校。

就没啥简单的题目。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5 + 5;
int cnt, fa[N], p[N], flag[N];
ll num[N];
vector<int> e[N];

int find(int son) {
	int root = son;
	while (fa[root] != root)	root = fa[root];
	while (root != son) {
		int t = son;
		fa[son] = root;
		son = fa[t];
	}
	return root;
}

void join(int a,int b) {
	int root1 = find(a), root2 = find(b);
	if (root1 != root2)	fa[root1] = root2, cnt--;
}

int cmp(int a, int b) {
	return num[a] > num[b];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		for (int i = 1; i <= n; i++)
			flag[i] = 0, e[i].clear(), fa[i] = p[i] = i, cin >> num[i];
		for (int i = 1; i <= m; i++) {
			int l, r;
			cin >> l >> r;
			e[l].push_back(r), e[r].push_back(l);
		}
		sort(p + 1, p + 1 + n, cmp);
		cnt = 1;
		ll ans = 0;
		flag[p[1]] = 1;
		for (int i = 2; i <= n; i++) {
			ans += (ll)cnt * (num[p[i - 1]] - num[p[i]]);
			cnt++;
			for (auto x : e[p[i]]) {
				int u = p[i];
				if (!flag[x])	continue;
				join(u, x);
			}
			flag[p[i]] = 1;
		}
		ans += (ll)cnt * num[p[n]];
		cout << ans << endl;
	}
	return 0;
}