hdu 2485 Highways

题意:Flatopia岛要修路,这个岛上有n个城市,要求修完路后,各城市之间可以相互到达,且修的总
路程最短.
求所修路中的最长的路段

最小生成树的一道题,很裸的一道题,不知道为什么就是编译过不了。

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int w[200000],u[200000],v[200000],p[510],r[200000];

int cmp(const int i,const int j)
{
    return w[i]<w[j];
}

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

int main()
{
    int a;
    cin >> a;
    while(a--)
    {
        memset(w,200000,0);
        memset(u,200000,0);
        memset(v,200000,0);
        int b;
        cin >> b;
        int temp =0,count = 1;
        for(int i =1; i<= b;i++)
        {
            for(int j = 1; j<= i;j++)
            {
                cin >> temp;
            }
            for(int j = i+1;j<= b;j++)
            {
                u[count] = i;
                v[count] = j;
                cin >> w[count++];
                //cout<< w[count-1]<< endl;
            }
        }
        int ans = 0;
        for(int i = 0; i< 510;i++)
        {
            p[i] = i;
        }
        for(int i =0; i <= b;i++)
        {
            r[i] = i;
        }
        sort(r+1,r+b+1,cmp);
        /*for(int i = 1; i <= 3;i++)
        cout<< w[r[i]]<< endl;*/
        for(int i = 1;i<= b;i++)
        {
            int e = r[i];
            int x= find(u[e]);
            int y = find(v[e]);
            if(x!= y)
            {
                ans = w[e];
                p[x] = y;
            }
        }
        cout<< ans << endl;
    }
    return 0;
}

  

原文地址:https://www.cnblogs.com/DUANZ/p/3870176.html