hrbust 1795发现王国之旅 【最小生成树】

发现王国之旅 Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 30(17 users) Total Accepted: 17(15 users) Rating: Special Judge: No Description 暑期将至，壮壮和胖胖约定去“发现王国”游乐园游玩。壮壮看到过山车，跳楼机，海盗船等等已经激动得不能自控，胖胖却已经双腿发软了。 游乐园中的每个设施都是由一些道路连接的，并且不存在一个地方有两个游乐设施。游乐园中还有一个奇怪的规定，就是经过每条道路，都要买一张该道路的通行证，而且有了该通行证之后，该条道路可以随意经过，并且游乐园里每条道路的通行证票价都是一样。壮壮想玩遍所有的游乐设施，但是又想花尽可能少的钱买通行证。道路花钱的原因主要是因为道路上有许多有趣的东西可以观看，壮壮走每条道路都会获得一个欢乐值 Z ，但是每条道路的欢乐值只能获得一次，现在壮壮想要使得他获得的所有道路的欢乐值的乘积最大，请你帮帮他吧。 Input 输入 有多组输入数据，对于每组输入数据：第1行为整数n（2<=n<=100），表示游乐项目的数目。此后的n行，每行n个整数。第x+1行y列的整数表示经过x游乐设施到y游乐设施之间的道路可以获得的欢乐值z, z为实数（ 0<z<10）。 Output 输出 有n组输出，每组输出一个答案并换行，答案为刺激程度C乘积以e为底的对数，保留三位小数。 Sample Input 3 0 1.0 3.0 1.0 0 2.0 3.0 2.0 0 Sample Output 1.792 Hint math.h中ln(x)的数学表达式为log(x) 做出来的第一道四星水题 哈哈哈；

#include<bits/stdc++.h>
using namespace std;
int pre[10005];
int findx(int x)
{
    return pre[x] == x ? x : findx(pre[x]);
}
void join(int x, int y)
{
    int a = findx(x);
    int b = findx(y);
    if(a != b)
        pre[a] = b;
}
struct node
{
    int x, y;
    double val;
} xx[10005];
bool cmp(node a, node b)
{
    return a.val > b.val;
}
int main()
{
    int n;
    while(cin >> n)
    {
        for(int i = 0; i <= n; i++)
            pre[i] = i;
        double c;
        int mmm = 0;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                cin >> c;                              
                xx[mmm].x = i;
                xx[mmm].y = j;
                xx[mmm].val = log(c);
                mmm++;               
            }
        }
        sort(xx, xx + mmm, cmp);
        int times = 0;
        double ans = 0;
        for(int i = 0; i < mmm; i++)
        {
            if(findx(xx[i].x) != findx(xx[i].y))
            {
                join(xx[i].x, xx[i].y);
                ans += xx[i].val;
            }
        }
        printf("%.3lf
", ans);
    }
    return 0;
}