2022杭电多校十 1004-Average Replacement（猜结论+并查集）

题目链接：杭电多校10 - Virtual Judge

题目：

样例输入： 

2
2 1
1 2
1 2
4 2
1 2 3 4
1 2
3 4

样例输出：

1.500000
1.500000
1.500000
1.500000
3.500000 
3.500000

题意：有n人，其中有m对朋友关系。朋友的朋友并不算是朋友，现在，每个人的帽子上都有一个整数，每一轮游戏中，每个人帽子上的整数都会变成他及其所有朋友的帽子上的整数的平均值，这个数可能不是整数，给定一个结论，当游戏次数足够多时，所有人的整数将会固定不变，求出这些最终值。

分析：容易想到，游戏轮次足够多时，位于同一个连通块内的值是相同的，否则不可能固定不变，所以我们只需要讨论每个连通块内的最终值即可。此处的连通块是具有传递关系的，也就是说A与B是朋友关系，B与C是朋友关系，那么A与C也在一个连通块中。由于整数的变化是在朋友关系之间的，所以就猜测答案可能跟每个人的朋友个数以及连通块有关系，假设i有d[i]个朋友，属于find(i)连通块，最后通过打表验证发现，每个连通块内为一定值,又因为整个连通块内的数都是相同的，这样我们就能够求出连通块内的每一个数。

细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=3e5+10;
int a[N],fu[N],d[N],sz[N];
long long sum[N];
int find(int x)
{
	if(x!=fu[x]) return fu[x]=find(fu[x]);
	return fu[x];
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			sum[i]=d[i]=sz[i]=0;
			fu[i]=i;
		}
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			d[u]++;d[v]++;
			int fx=find(u),fy=find(v);
			if(fx!=fy)	fu[fy]=fx;
		}
		for(int i=1;i<=n;i++)
		{
			sum[find(i)]+=1ll*a[i]*(d[i]+1);
			sz[find(i)]+=d[i]+1;
		}
		for(int i=1;i<=n;i++)
			printf("%.6lf\n",1.0*sum[find(i)]/sz[find(i)]);
	}
	return 0;
}