poj1182

題意：http://poj.org/problem?id=1182

分析：并查集的經(jīng)典題目，在這題當(dāng)中，我們不僅要用并查集維護(hù)屬于同一類，同時還應(yīng)該用并查集維護(hù)被吃的關(guān)系。因?yàn)槲锓N屬于A,B,C三種，所以我們開一個n*3來進(jìn)行紀(jì)錄。然后如果是1的話，那分別合并到三個集合，如果是2的話，按照食物鏈的關(guān)系進(jìn)行合并。注意在合并之前我們需要進(jìn)行判斷，如果是1的話，要判斷該元素是否在另外兩類中出現(xiàn)過，如果是2的話，要判斷食物鏈?zhǔn)欠裼忻堋?/p> 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 const int maxn=50002; 15 int par[maxn*3],rankl[maxn*3]; 16 17 //并查集模板 18 void init(int n){ 19 for(int i=0;i<n;i++){ //初始化 20 par[i]=i; 21 rankl[i]=0; 22 } 23 } 24 25 int findl(int x){ //查找跟結(jié)點(diǎn) 26 if(x==par[x]){ 27 return x; 28 }else{ 29 return par[x]=findl(par[x]); 30 } 31 } 32 33 void unite(int x,int y){ //合并操作 34 x=findl(x); 35 y=findl(y); 36 if(x==y) return; 37 if(rankl[x]<rankl[y]){ 38 par[x]=y; 39 }else{ 40 par[y]=x; 41 if(rankl[x]==rankl[y]) rankl[x]++; 42 } 43 } 44 45 bool same(int x,int y){ //判斷是否在同一集合 46 return findl(x)==findl(y); 47 } 48 49 int main() 50 { 51 int n,k; 52 cin>>n>>k; 53 init(n*3); 54 int cnt=0; 55 for(int i=0;i<k;i++){ 56 int id,x,y; 57 scanf("%d%d%d",&id,&x,&y); 58 --x,--y; 59 if(x<0||y<0||n<=x||n<=y){ 60 cnt++; continue; 61 } 62 if(id==1){ 63 if(same(x,y+n)||same(x,y+2*n)){ 64 cnt++; 65 }else{ 66 unite(x,y); 67 unite(x+n,y+n); 68 unite(x+2*n,y+2*n); 69 } 70 }else{ 71 if(same(x,y)||same(x,y+2*n)){ 72 cnt++; 73 }else{ 74 unite(x,y+n); 75 unite(x+n,y+2*n); 76 unite(x+2*n,y); 77 } 78 } 79 } 80 cout<<cnt<<endl; 81 return 0; 82 } View Code

?

poj2236

題意：因?yàn)榈卣?#xff0c;使網(wǎng)絡(luò)不能聯(lián)通，經(jīng)過維修之后可以連通不超過距離d的網(wǎng)絡(luò)，任何網(wǎng)絡(luò)可以作為其他兩個網(wǎng)絡(luò)的中介。O表示維修，S表示是否連通

分析：裸的并查集，O的時候把符合要求的并入集合，S的時候看是否屬于同一個集合即可。注意不行的時候是FAIL，2333

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 const int maxn=1010; 15 int par[maxn],rankl[maxn]; 16 17 void init(int n){ 18 for(int i=0;i<=n;i++){ 19 par[i]=i; 20 rankl[i]=0; 21 } 22 } 23 24 int findl(int x){ 25 if(x==par[x]) 26 return x; 27 else{ 28 return par[x]=findl(par[x]); 29 } 30 } 31 32 void unite(int x,int y){ 33 x=findl(x); 34 y=findl(y); 35 if(x==y) return; 36 if(rankl[x]<rankl[y]){ 37 par[x]=y; 38 }else{ 39 par[y]=x; 40 if(rankl[x]==rankl[y]) rankl[x]++; 41 } 42 } 43 44 bool same(int x,int y){ 45 return findl(x)==findl(y); 46 } 47 48 int n,d; 49 bool judge(int x1,int y1,int x2,int y2){ 50 if((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)>d*d) 51 return false; 52 else return true; 53 } 54 55 struct p{ 56 int id,x,y,vis; 57 }s[maxn]; 58 int main() 59 { 60 cin>>n>>d; 61 init(n); 62 for(int i=1;i<=n;i++){ 63 cin>>s[i].x>>s[i].y; 64 s[i].id=i; 65 s[i].vis=0; 66 } 67 char ch[5]; 68 while(scanf("%s",ch)!=EOF){ 69 int a,b; 70 if(ch[0]=='O'){ 71 cin>>a; 72 s[a].vis=1; 73 for(int i=1;i<=n;i++){ 74 if(judge(s[i].x,s[i].y,s[a].x,s[a].y)&&s[i].vis&&i!=a) 75 unite(i,a); 76 } 77 }else if(ch[0]=='S'){ 78 cin>>a>>b; 79 if(same(a,b)) 80 cout<<"SUCCESS"<<endl; 81 else 82 cout<<"FAIL"<<endl; 83 } 84 } 85 return 0; 86 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/wolf940509/p/5484963.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的5月12日的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。