[JSOI2010 Group 部落划分]并差集、排序

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1821
【算法分析】
就是把边权从小到大排序，然后从前面搞下来，用并差集判断剩下的独立块有多少个？
如果【其它】
WA了N遍= =。
if (Num写成了
if (Num头脑有点不清醒啊。。。
【CODE】
#include #include #include #include #define sqr(x) ((x)*(x))
const int N=1005;
struct Point{int x,y;}a[N];
struct edge{int x,y,w;}g[N*N];
int n,part,m;
int f[N];

int dis(Point A,Point B){
return sqr(A.x-B.x)+sqr(A.y-B.y);
}

void input(){
scanf("%d%d",&n,&part);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
m=0;
for (int i=1;i for (int j=i+1;j<=n;j++){
g[m].x=i;
g[m].y=j;
g[m].w=dis(a[i],a[j]);
++m;
}
}

int cmp(const void *A,const void *B){
return ((edge*)A)->w-((edge*)B)->w;
}

int GF(int k){
if (f[k]==k) return k;
else return f[k]=GF(f[k]);
}

int solve(){
int Num=n;
for (int i=1;i<=n;i++) f[i]=i;
for (int i=0;;i++){
edge &p=g[i];
if (GF(p.x)!=GF(p.y)){
f[f[p.x]]=f[p.y];
Num–;
if (Num }
}
}

int main(){
input();
qsort(g,m,sizeof(edge),cmp);
printf("%.2lfn",sqrt(1.0*solve()));
}