http://acm.hdu.edu.cn/showproblem.php?pid=1213
题意就是说，有n个人参加的party，要准备多少张桌子，使得任意桌子上坐的人都是有联系的。
所谓有联系的就是说：比如A 和 B，如果他们两认识，或者存在一些人 C D E...使得A 、B能够认识。
求最少要准备的桌子的数量。
解法：直接用并查集算法解决。
分析：把昨天的代码拿来稍微改了下，果断ac。水题飘过。
View Code
// I'm lanjiangzhou //C #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include <math.h> #include <time.h> //C++ #include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> using namespace std; #define INF 0x3f3f3f3f const int maxn = 2010; struct node{ int u,v; int w; }edges[maxn*4]; int pa[maxn]; int n,m; int x[maxn],y[maxn]; int sumweight=0; int num; //初始化 void UFset(){ for(int i=1;i<=n;i++){ pa[i]=-1; } } //查找 int findset(int x){ int s; for(s=x;pa[s]>=0;s=pa[s]); while(s!=x){ int tmp=pa[x]; pa[x]=s; x=tmp; } return s; } //合并 void Union(int R1,int R2){ int r1=findset(R1), r2=findset(R2); int tmp=pa[r1]+pa[r2]; if(pa[r1]>pa[r2]){ pa[r1]=r2; pa[r2]=tmp; } else { pa[r2]=r1; pa[r1]=tmp; } } int cmp(const void*a,const void*b){ node aa=*(const node*)a; node bb=*(const node*)b; if(aa.w>bb.w) return 1; else return -1; } void Kruskal(){ // int num=0; int u,v; UFset(); for(int i=0;i<m;i++){ u=edges[i].u; v=edges[i].v; if(findset(u)!=findset(v)){ //sumweight+=edges[i].w; num++; Union(u,v); } if(num>=n-1) break; } } int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); int u,v,w; for(int i=0;i<m;i++){ scanf("%d%d",&u,&v); edges[i].u=u; edges[i].v=v; //edges[i].w=w; edges[i].u=v; edges[i].v=u; //edges[i].w=w; } num=0; qsort(edges,m,sizeof(edges[0]),cmp); // for(int i=0;i<m;i++){ // printf("edges[i].w=%d\n",edges[i].w); // } sumweight=0; Kruskal(); printf("%d\n",n-num); } return 0; }