TIOJ 1327 最小格子生成樹-EXTREME ( TFcis10 留社考 )

poao899    1092K    234MS    G++     1.64K     2009-11-11 15:48:24                                            .

原來每條邊只能垂直或水平=口=
















蚯蚓：雖然貌似完全圖，不過實際只有2V條邊














//*******************************

#include<stdio.h>
#include<algorithm>
#define V 100005
#define sw(i,j) {tmp=i;i=j;j=tmp;}
int getint(){
    int g=0,c=getchar(),s=1;
    while(c==10||c==32)c=getchar();
    if(c=='-')s=-1,c=getchar();
    while(c>='0'&&c<='9'){
        g=g*10+c-48;
        c=getchar();
    }
    return g*s;
}
int root[V],tmp;
int find(int a){
    return a==root[a]?a:root[a]=find(root[a]);
}
struct point{
    int x,y,order;
    bool operator<(const point &b)const{
        return x==b.x?y<b.y:x<b.x;
    }
    void get(int i){
        x=getint();
        y=getint();
        order=i;
    }
}P[V];
struct edge{
    int i,j,len;
    bool operator<(const edge &b)const{
        return len<b.len;
    }
   
}E[V*3];
int n,t,edgeCnt,edgeUsed;
long long MSTCost;
void set(int i,int j,int len){
    edge *p=&E[edgeCnt++];
    p->i=i;
    p->j=j;
    p->len=len;
}
main(){
    t=getint();
    while(t--){
        //Initialize
        edgeCnt=edgeUsed=0;
        MSTCost=0;
        for(int i=0;i<V;i++)
            root[i]=i;
        //Input
        n=getint();
        for(int i=0;i<n;i++)
            P[i].get(i);
        //Sort & Build Edge
        std::sort(P,P+n);
        for(int i=1;i<n;i++){
            if(P[i].x==P[i-1].x){
                set(P[i].order,P[i-1].order,P[i].y-P[i-1].y);
            }
            sw(P[i-1].x,P[i-1].y);
        }
        sw(P[n-1].x,P[n-1].y);
        std::sort(P,P+n);
        for(int i=1;i<n;i++){
            if(P[i].x==P[i-1].x){
                set(P[i].order,P[i-1].order,P[i].y-P[i-1].y);
            }
        }
        //Kruskal
        std::sort(E,E+edgeCnt);
        for(int i=0;i<edgeCnt&&edgeUsed<n-1;i++){
            int ri=find(E[i].i);
            int rj=find(E[i].j);
            if(ri!=rj){
                edgeUsed++;
                MSTCost+=E[i].len;
                root[ri]=rj;
            }
        }
        printf("%I64d\n",MSTCost);
    }
}