Codeforces 437D The Child and Zoo（并查集）

[Codeforces 437D The Child and Zoo](http://codeforces.com/problemset/problem/437/D)
题目大意：
有一张连通图，每个点有对应的值。定义从p点走向q点的其中一条路径的花费为途径点的最小值。定义f(p,q)为从点p走向点q的所有路径中的最大花费。累加每一对p,q的f(p,q)，并求平均值。
乍一看以为是对图的搜索，但搜索求和的过程肯定会超时。这一题巧妙的用到了[并查集](http://www.cnblogs.com/orangee/p/8686470.html)，因此做简单记录。
思路：
将边的权值定义为两点间的较小值，对边进行降序排序。排序后将每条边的两点进行并查集维护，由于排了序，所以可以保证两个点所属集合合并时，num[u]、num[w]、v三者的乘积得到是两个集合中的点两两组合的f(u,w)的总和（因为此时两集合中任意各取一点都满足所走路径的花费为v（当前边的权值)，且是这两点所有路径中花费最大的），这也是个人感觉该解法的巧妙之处（其中num[i]表示根为i的集合的大小）。总之感觉这题对问题的转化真的很有趣。
PS：要注意累加时中间过程可能溢出，因此可以强制转化其中一个数为double，从而使其他数跟着类型提升，防止溢出。
代码：
```C++
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef map M;
typedef queue Q;
typedef vector V;
typedef pair P;
const int maxn=5*100000;
int a[maxn],p[maxn],num[maxn];//num[i]表示根为i的集合的大小
struct edge
{
int u,w,v;
};
bool cmp(const edge& a,const edge& b)
{
return a.v>b.v;
}
edge e[maxn];
double sum=0;
void init(int n)
{
for (int i=0;i>n>>m;
//输入
for (i=1;i</font>

巴特西

Codeforces 437D The Child and Zoo（并查集）

最新文章

热门文章