不想看模板，想直接看题目的请戳下面目录：
目录：
hdu 1213 how many tables【传送门】
hdu 1232 畅通工程 【传送门】
poj 2236 wireless network 【传送门】
poj 1703 find them, catch them 【传送门】
先上模板：
1 #define maxn 根据编号需要 2 int per[maxn],rank[maxn]; 3 4 void init(int n) 5 { 6 int i; 7 for(i=1;i<=n;i++) 8 { 9 per[i]=i;rank[i]=0 10 } 11 12 } 13 14 int find(int x) 15 { 16 if(x==per[x]) 17 return x; 18 return per[x]=find(per[x]); 19 } 20 21 void unite(int x,int y) 22 { 23 x=find(x); 24 y=find(y); 25 if(x==y) 26 return; 27 if(rank[x]>rank[y]) 28 per[y]=x; 29 else 30 { 31 per[x]=y; 32 if(rank[x]==rank[y]) 33 rank[y]+=1; 34 } 35 } 36 37 bool same(int x,int y) 38 { 39 return find(x)==find(y); 40 }
并查集详解请访问：（通俗易懂解释）
接下来来看几个例子：
hdu 1213 how many tables
题目大意：有一个人过生日，请到了他的诸多朋友，但是这些朋友之间有的认识，有的不认识。这个人想尽可能的把相互之间认识的人凑到一张桌子上，不认识的人则去另一张桌子。朋友们互相认识的规则是：比如a认识b，b认识c，那么a，b，c就可以凑到一桌子上。现在问：他的朋友们以这样的规则能凑够几桌。
解题思路：运用并查集，把相互认识的人都联合一下，到最后计算数组中有几个per值等于自身的人就可以了。
1 #include<iostream> 2 3 using namespace std; 4 5 int f[1005]; 6 7 void init(int n) 8 { 9 for(int i=1;i<=n;i++) 10 f[i]=i; 11 } 12 13 int find(int a) 14 { 15 while(a!=f[a]) 16 { 17 a=f[a]; 18 } 19 return a; 20 } 21 22 void combin(int a,int b) 23 { 24 int ta,tb; 25 ta=find(a); 26 tb=find(b); 27 28 if(ta!=tb) 29 f[ta]=tb; 30 } 31 32 int answer(int n) 33 { 34 int sum=0; 35 for(int i=1;i<=n;i++) 36 if(f[i]==i) 37 sum++; 38 return sum; 39 } 40 41 int main() 42 { 43 44 int t; 45 cin >> t; 46 while(t--) 47 { 48 int n,m; 49 cin >> n >> m; 50 init(n); 51 int a,b; 52 for(int i=0;i<m;i++) 53 cin >> a >> b,combin(a,b); 54 cout << answer(n) << endl ; 55 } 56 57 return 0; 58 }
hdu 1232 畅通工程
此处略去题目大意……
解题思路：其实这个题目和上一个题异曲同工，就是变换了一下条件，我们假设村子是上题的朋友，那么路就是朋友们之间的关系，那么两堆朋友之间连线，其实只需要一次就可以了，同样，三堆朋友之间要想相互认识，只需要两个关系就可以了，所以我们很容易可以得出朋友们要想都认识，只需要把朋友堆数 – 1 就可以了。
代码只需要将上题的输出结果-1即可 ，不再贴出。
poj 2236 wireless network
题目大意：一片废弃的地方，acm协会正在进行救援，可是所有电脑的通信设施都被破坏了，被修复好的电脑的信号传输距离只有d米，现在给出所有电脑的坐标，然后给出指令s与o，s后跟两个数字代表两个电脑的编号，询问这两台电脑是否能通信，如果能则输出success，否则输出fall；o后跟一个编号，代表修好一定电脑。
解题思路：此题运用并查集，在修复好一台电脑之后遍历所有修好的电脑，如果两点间距离小于d米，则连通两个点；遇到s的时候只需要判断是否连通即可。
1 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 #define maxn 1005 5 6 //坐标 7 struct pos{ 8 int x,y; 9 int par_id; //父辈id 10 int rank; //树的高度 11 }; 12 13 struct pos par[maxn]; //记录父亲 14 bool isok[maxn]; //是否被修复成功 15 16 float distance(struct pos a,struct pos b) 17 { 18 float dis=sqrt(fabs(a.x-b.x)*fabs(a.x-b.x)+fabs(a.y-b.y)*fabs(a.y-b.y)); 19 return dis; 20 } 21 22 void init(int n) 23 { 24 for(int i=1;i<=n;i++) 25 { 26 par[i].par_id=i; 27 par[i].rank=0; 28 isok[i]=false; 29 } 30 } 31 32 //查树根 33 int find(int x) 34 { 35 if(par[x].par_id==x) 36 return x; 37 else 38 return par[x].par_id=find(par[x].par_id); 39 } 40 41 //合并 42 void unite(int x,int y) 43 { 44 x=find(x); 45 y=find(y); 46 if(x==y) 47 return; 48 if(par[x].rank<par[y].rank) 49 par[x].par_id=y; 50 else{ 51 par[y].par_id=x; 52 if(par[x].rank==par[y].rank) 53 par[x].rank++; 54 } 55 } 56 57 //判断x和y是不是同一个集合 58 bool same(int x,int y) 59 { 60 return find(x)==find(y); 61 } 62 63 int main() 64 { 65 int n,d; 66 char c; 67 cin >> n >> d; 68 init(n); 69 for(int i=1;i<=n;i++) 70 { 71 int x,y; 72 cin >> x >> y; 73 par[i].x=x; 74 par[i].y=y; 75 } 76 77 while(cin >> c) 78 { 79 int p,q; 80 if(c=='o') 81 { 82 cin >> p; 83 isok[p]=true; 84 for(int i=1;i<=n;i++) 85 { 86 if(isok[i]==true&&i!=p) 87 { 88 struct pos a,b; 89 a.x=par[i].x; 90 a.y=par[i].y; 91 a.par_id=par[i].par_id; 92 b.x=par[p].x; 93 b.y=par[p].y; 94 b.par_id=par[p].par_id; 95 if(distance(a,b)<=d) 96 { 97 // cout << distance(a,b) << endl; 98 unite(p,i); 99 } 100 101 } 102 } 103 } 104 else if(c=='s') 105 { 106 cin >> p >> q; 107 if(same(p,q)) 108 cout << "successn"; 109 else 110 cout << "failn"; 111 } 112 // for(int i=1;i<=n;i++) 113 // cout << par[i].par_id << " "; 114 // cout << endl; 115 } 116 return 0; 117 }
poj 1703 find them, catch them
题目大意：有两个帮派，警察现在抓住了n个罪犯，输入字母a或d，后面跟着两个罪犯的编号。如果字符是a，则代表这一次询问：如果不是一个帮派，则输出“in different gangs.”；是一个帮派输出”in the same gang.”；否则输出“not sure yet.”。如果是字符d，那就代表着后面的两个编号不属于一个帮派！
解题思路：需要一个标记数组vis，用来标记两个罪犯(a,b)不属于同一个帮派，如果标记数组两个罪犯都为0则代表不确定是哪个帮派，并且让vis[a]=b,vis[b]=a；如果vis[a]==0&&vis[b]!=0，则让vis[b]=a，并且连通a,vis[b]；如果vis[b]==0&&vis[a]!=0，则让vis[a]=b，并且连通b,vis[a]；最后一种情况是a与b的标记数组都不为0，那么连2019-07-21通a,vis[b]，连通b,vis[a]最后判断即可。
1 //#include<iostream> 2 //using namespace std; 3 #include<stdio.h> 4 #define maxn 100010 5 6 int per[maxn],rank[maxn],vis[maxn]; 7 8 void init(int n) 9 { 10 int i; 11 for(i=1;i<=n;i++) 12 { 13 per[i]=i;rank[i]=0;vis[i]=0; 14 } 15 16 } 17 18 int find(int x) 19 { 20 if(x==per[x]) 21 return x; 22 return per[x]=find(per[x]); 23 } 24 25 void unite(int x,int y) 26 { 27 x=find(x); 28 y=find(y); 29 if(x==y) 30 return; 31 if(rank[x]>rank[y]) 32 per[y]=x; 33 else 34 { 35 per[x]=y; 36 if(rank[x]==rank[y]) 37 rank[y]+=1; 38 } 39 } 40 41 int same(int x,int y) 42 { 43 if(find(x)==find(y)) 44 return 1; 45 46 } 47 48 int main() 49 { 50 // ios::sync_with_stdio(false); 51 int t; 52 scanf("%d",&t); 53 // cin >> t; 54 while(t--) 55 { 56 int n,m; 57 scanf("%d%d",&n,&m); 58 // cin >> n >> m; 59 init(n); 60 while(m--) 61 { 62 int a,b; 63 char c[2]; 64 scanf("%s",c); 65 //getchar(); 66 scanf("%d%d",&a,&b); 67 //cin >> c >> a >> b; 68 //联立 69 //printf("%cn",c); 70 if(c[0]=='d') 71 { 72 if(vis[a]==0&&vis[b]==0) 73 { 74 vis[a]=b; 75 vis[b]=a; 76 } 77 else if(vis[a]==0) 78 { 79 vis[a]=b; 80 unite(a,vis[b]); 81 } 82 else if(vis[b]==0) 83 { 84 vis[b]=a; 85 unite(b,vis[a]); 86 } 87 else{ 88 unite(a,vis[b]); 89 unite(b,vis[a]); 90 } 91 } 92 else{ 93 if(same(a,b)) 94 printf("in the same gang.n"); 95 //cout << "in the same gang.n"; 96 else if(same(a,vis[b])) 97 //cout << "in different gangs.n"; 98 printf("in different gangs.n"); 99 else 100 printf("not sure yet.n"); 101 //cout << "not sure yet.n"; 102 } 103 } 104 } 105 106 return 0; 107 }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/602630.html