[HDOJ3371 Connect the Cities]并差集、最小生成树、启发式合并

【题目大意】

有点已经成一个块了，让你加最少费用的边，使得它整个图成为一个连通块。

【算法分析】

经典最小生成树。

用并差集处理块，然后排序一下搞个kruskal。

但是很容易TLE。于是我加了那个启发式合并。

【其它】

尽管如此，我用G++交还是TLE,C++500多MS。

可能并差集写成非递归会好点。

【CODE】

#include #include #include #include #include #include using namespace std;
const int N=1000000;
int Tc,n,m,k,done,ans;
int f[N],d[N][3];
int num[N];

int gf(int p){
    if (f[p]==p) return p;
    f[p]=gf(f[p]);
    return f[p];
}

void input(){
    done=0; ans=0;
    int i,j,t,one,x;
    scanf("%d%d%d",&n,&m,&k);
    for (i=1;i<=n;i++){
        f[i]=i;
        num[i]=1;
    }
    for (i=1;i<=m;i++)
      scanf("%d%d%d",&d[i][0],&d[i][1],&d[i][2]);
    for (i=1;i<=k;i++){
        scanf("%d%d",&t,&one);
        for (j=1;j          scanf("%d",&x);
          if (gf(x)!=gf(one)){
            if (num[f[x]]                num[f[one]]+=num[f[x]];
                f[f[x]]=f[one];
            }
            else{
                num[f[x]]+=num[f[one]];
                f[f[one]]=f[x];
            }
            done++;
          }
        }
    }
}

int cmp(const void *x,const void *y){
    return ((int *)x)[2]-((int *)y)[2];
}

void work(){
    if (done==n-1) return;
    qsort(d[1],m,sizeof(int)*3,cmp);
    for (int i=1;i<=m;i++){
      int &x=d[i][0],&y=d[i][1];
      if (gf(x)!=gf(y)){
          if (num[f[x]]              num[f[y]]+=num[f[x]];
              f[f[x]]=f[y];
          }
          else{
              num[f[x]]+=num[f[y]];
              f[f[y]]=f[x];
          }

          done++;
          ans+=d[i][2];
          if (done==n-1) return;
      }
    }
}

void output(){
    if (done==n-1) printf("%dn",ans);
              else printf("-1n");
}

int main(){
    cin >> Tc;
    for (int i=1;i<=Tc;i++){
        input();
        work();
        output();
    }
}