Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

求大牛指点 为什么re

Posted by lsg0827 at 2011-07-28 21:13:26 on Problem 1797
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 1000005
int father[1005],num[1005];
int m,n,c,total;
struct node
{
    int x;
    int y;
    int w;
}edge[MAX];
bool  cmp(node a,node b)
{
    return a.w>b.w;
}
void make_set()
{
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
        num[i]=1;
    }
}
int find_set(int x)
{
    if(x!=father[x])
    {
        father[x]=find_set(father[x]);
    }
    return father[x];
}
void Union(int a,int b)
{
    int x=father[a];
    int y=father[b];
    if(num[x]>num[y])
    {
        father[y]=x;
        num[x]+=num[y];
    }
    else
    {
        father[x]=y;
        num[y]+=num[x];
    }

}
int main()
{
    scanf("%d",&c);
    for(int k=1;k<=c;k++)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w);
        }
        make_set();
        sort(edge+1,edge+m+1,cmp);
        for(int i=1;i<=m;i++)
        {
            if(find_set(1)==find_set(n))
            {
                total=edge[i].w;
                break;
            }
            else
            {
                Union(edge[i].x,edge[i].y);
            }
        }
        printf("Scenario #%d:\n",k);
        printf("%d\n",total);
        printf("\n");
    }
    return 0;
}








Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator