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:第一次krustal,一次A,留代码做纪念

Posted by MikuGhoul at 2016-08-27 16:40:30 on Problem 2485
In Reply To:第一次krustal,一次A,留代码做纪念 Posted by:sunyi740 at 2016-03-29 22:14:48
> #include<iostream>
> #include<cstdlib>
> using namespace std;
> int n,k;
> struct edge
> {
>     int u;
>     int v;
>     int w;
> };
> edge p[500*500];
> 
> int cmp(const void *a,const void *b)
> {
>     edge *p1=(edge *)a;
>     edge *p2=(edge *)b;
>     return p1->w-p2->w;
> }
> 
> void kruskal()
> {
>     int flag[500];
>     for(int i=1;i<=n;i++)
>         flag[i]=i;
>     qsort(p,k,sizeof(edge),cmp);
>     int maxn=0;
>     for(int i=1;i<=k;i++)
>     {
>         if(flag[p[i].u]!=flag[p[i].v])
>         {
>             int t=flag[p[i].u];
>             for(int j=1;j<=n;j++)
>                 if(flag[j]==t) flag[j]=flag[p[i].v];
>             if(p[i].w>maxn) maxn=p[i].w;
> 
>             //cout<<i<<' '<<maxn<<endl;
>         }
>     }
>     cout<<maxn<<endl;
> }
> 
> 
> int main()
> {
>     int m;
>     cin>>m;
>     while(m--)
>     {
>         cin>>n;
>         k=0;
>         for(int i=1;i<=n;i++)
>             for(int j=1;j<=n;j++)
>         {
>             k++;
>             p[k].u=i;
>             p[k].v=j;
>             cin>>p[k].w;
>         }
>         kruskal();
>     }
> }

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