#include<stdio.h>
#include<stdlib.h>
int edges[200000][3];  //边表 
int collec[200000]={0};//并查集
void edgesort(int edges[][3],int fir,int las)//快排 
{
     int bas=edges[fir][0];
     int i=fir; int j=las;
     int temp1,temp2;
     temp1=edges[fir][1];
     temp2=edges[fir][2];
     while(i<j)
     {
        while((edges[j][0]>=bas)&&(i<j)) j--;
        edges[i][0]=edges[j][0];
        edges[i][1]=edges[j][1];
        edges[i][2]=edges[j][2];
        while((edges[i][0]<=bas)&&(i<j)) i++;
        edges[j][0]=edges[i][0];
        edges[j][1]=edges[i][1];
        edges[j][2]=edges[i][2];
     }
     edges[i][0]=bas;
     edges[i][1]=temp1;
     edges[i][2]=temp2;
     if(fir<i) edgesort(edges,fir,i-1);
     if(i<las) edgesort(edges,i+1,las);
}
int in(int p1,int p2)   /// 查集 1为环 
{
    int root1,root2;
    root1=p1;root2=p2;
    while(collec[root1]!=-1) root1=collec[root1];
    while(collec[root2]!=-1) root2=collec[root2];
    if(root1==root2) return 1;
    else return 0;
}
void link(int p1,int p2)//求并集 
{
    int root1,root2;
    root1=p1;root2=p2;
    while(collec[root1]!=-1) root1=collec[root1];
    while(collec[root2]!=-1) root2=collec[root2];
    collec[root2]=root1;
}
long krus(int P,int E)
{
     long total=0;
     int i,j,flag=0;
     int now;
     for(i=1;i<=P;i++) collec[i]=-1;
     edgesort(edges,1,E);
     for(now=E;now>=1;now--)
     {
        if( in( edges[now][1],edges[now][2] )==1) continue;
        link(edges[now][1],edges[now][2]);
        total+=edges[now][0];
     }
     return total;
}
int main()
{
    int wo,ma,r;
    int n;
    int i,j;
    int s,e,l;
    ////////
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
       edges[0][0]=0;
       scanf("%d%d%d",&wo,&ma,&r);
       for(j=1;j<=r;j++)
       {
         scanf("%d%d%d",&s,&e,&l);
         s++; e++;e+=wo;
         edges[j][0]=l;
         edges[j][1]=s;
         edges[j][2]=e;
       }
       printf("%ld\n",10000*(wo+ma)-krus(wo+ma,r));
    }
    return 0;
}

• Re:为什么我的kruskal TLE? (9) rush_again 2010-03-24 09:18:23
  • kruskal是可以过的，写复杂当然过不了，最好是优化处理一下 (13) 0810311106 2010-08-01 16:49:25
    • Re:kruskal是可以过的，虽然你这里加入了并查集优化，写复杂当然过不了 (0) 0810311106 2010-08-01 16:50:42