【并查集】模板 + 【HDU 1213、HDU 1232、POJ 22…
2019-08-16 07:51:58来源:博客园 阅读 ()
【并查集】模板 + 【HDU 1213、HDU 1232、POJ 2236、POJ 1703】例题详解
不想看模板,想直接看题目的请戳下面目录:
目录:
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 }View Code
并查集详解请访问:(通俗易懂解释)
https://blog.csdn.net/lesileqin/article/details/96703143
接下来来看几个例子:
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 }View Code
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 << "SUCCESS\n"; 109 else 110 cout << "FAIL\n"; 111 } 112 // for(int i=1;i<=N;i++) 113 // cout << par[i].par_id << " "; 114 // cout << endl; 115 } 116 return 0; 117 }View Code
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("%c\n",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 }View Code
原文链接:https://www.cnblogs.com/lesileqin/p/11221288.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
- 单调队列模板【附例题】 2020-05-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash