• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CF437D The Child Zoo

开发技术 开发技术 4小时前 1次浏览

CF437D The Child Zoo

思路

做过ABC214D,以及货车运输的前半部分,再加上点权转边权,这道题就解决了。肯定是要形成最大生成树,之后考虑如何计算总的(f)值,考虑拆贡献计算每条边的贡献,在生成树的过程中计算即可。(ABC的那道题)。此题得到解决。
加边加边并查集查询。

代码

#include <bits/stdc++.h>
#define N 100010
#define int long long
using namespace std;

int n,m,tot;
int a[N],p[N],sz[N];
struct Edge{
	int u,v,w;
	bool operator < (const Edge &B) const
	{
		return w > B.w;
	}
}edge[N];

inline int find(int x)
{
	return p[x] != x ? p[x] = find(p[x]) : p[x];
}

inline void Merge(int u,int v,int w)
{
	tot += sz[u] * sz[v] * w * 2;
	sz[u] += sz[v];
	p[v] = u;
}

signed main()
{
	std::ios::sync_with_stdio(false);
	
	cin >> n >> m;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1;i <= m;i++){
		int u,v;
		cin >> u >> v;
		edge[i] = {u,v,min(a[u],a[v])};
	}
	sort(edge + 1,edge + 1 + m);
	for(int i = 1;i <= n;i++) p[i] = i,sz[i] = 1;
	for(int i = 1;i <= m;i++){
		int u = edge[i].u,v = edge[i].v,w = edge[i].w;
		u = find(u),v = find(v);
		if(u == v) continue;
		Merge(u,v,w);
	}
	printf("%.6lfn",1.0 * tot / (n * (n - 1)));
	return 0;
} 

程序员灯塔
转载请注明原文链接:CF437D The Child Zoo
喜欢 (0)