poj2485&&poj2395 kruskal

题意:最小生成树的最大边最小，sort从小到大即可

poj2485

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

#define maxn 505

int map[maxn][maxn],pa[],num,n;

struct node

{

    int x;

    int y;

    int val;

}s[];

bool cmp(node a,node b)

{

    return a.val<b.val;

}

void init()

{

    int i,j;

    scanf("%d",&n);

    for(i=;i<=n;i++)

        for(j=;j<=n;j++)

            scanf("%d",&map[i][j]);

    for(i=;i<=n;i++)

        pa[i]=i;

}

void makemap()

{

    int i,j;

    num=;

    for(i=;i<=n;i++)

        for(j=i+;j<=n;j++)

        {

            s[num].x=i;s[num].y=j;s[num++].val=map[i][j];

        }

}

int find(int x)

{

    if(x!=pa[x])

        pa[x]=find(pa[x]);

    return pa[x];

}

void kruskal()

{

    int i,j,ans=;

    sort(s,s+num,cmp);

    for(i=;i<num;i++)

    {

        int l1,l2;

        l1=find(s[i].x);l2=find(s[i].y);

        if(l1!=l2)

        {

            pa[l1]=l2;

            ans=s[i].val;

        }

    }

    printf("%d\n",ans);

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        init();

        makemap();

        kruskal();

    }

    return ;

}

poj2395

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

#define maxn 2002

int pa[maxn],num,n;

struct node

{

    int x;

    int y;

    int val;

}s[];

bool cmp(node a,node b)

{

    return a.val<b.val;

}

void init()

{

    int i;

    for(i=;i<=n;i++)

        pa[i]=i;

}

int find(int x)

{

    if(x!=pa[x])

        pa[x]=find(pa[x]);

    return pa[x];

}

void kruskal()

{

    int i,j,ans=;

    sort(s,s+num,cmp);

    for(i=;i<num;i++)

    {

        int l1,l2;

        l1=find(s[i].x);l2=find(s[i].y);

        if(l1!=l2)

        {

            pa[l1]=l2;

            ans=s[i].val;

        }

    }

    printf("%d\n",ans);

}

int main()

{

    int i,j;

    while(scanf("%d%d",&n,&num)!=EOF)

    {

        init();

        for(i=;i<num;i++)

            scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].val);

        kruskal();

    }

    return ;

}