POJ 2236 Wireless Network ||POJ 1703 Find them, Catch them 并查集
POJ 2236 Wireless Network
http://poj.org/problem?id=2236
题目大意:
给你N台损坏的电脑坐标,这些电脑只能与不超过距离d的电脑通信,但如果x和y均能C通信,则x和y可以通信。现在给出若干个操作,
O p 代表修复编号为p的电脑
S p q代表询问p和q是不是能通信。
思路:
并查集即可。。
如果修复了一台电脑,则把与它相连距离不超过d的且修复了的放在一个集合里面。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN=1000+10; int fa[MAXN],n,d; bool canuse[MAXN]; int find(int cur) { return fa[cur]<0? cur: fa[cur]=find(fa[cur]); } struct computers { int x,y; }a[MAXN]; bool ok(int x1,int y1,int x2,int y2) { return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) <= d*d; } int main() { memset(fa,-1,sizeof(fa)); memset(canuse,0,sizeof(canuse)); scanf("%d%d",&n,&d); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); char cmd[10]; int p,q; while(~scanf("%s",cmd)) { if(cmd[0]==‘O‘) { scanf("%d",&p); int root=find(p); for(int i=1;i<=n;i++) { if(i==p) continue; if(ok(a[i].x,a[i].y,a[p].x,a[p].y) && canuse[i]) { int root1=find(i); int root2=find(p); if(root1!=root2) fa[root1]=root2; } } canuse[p]=true; } else { scanf("%d%d",&p,&q); int rootp=find(p); int rootq=find(q); if(rootp==rootq) printf("SUCCESS\n"); else printf("FAIL\n"); } } return 0; }
POJ 1703 Find them, Catch them
http://poj.org/problem?id=1703
题目大意:
xx城市有两个帮派,给你m条信息,D a b表示a和b不在一个帮派里。A a b时要求输出a和b是不是在一个帮派里。(在/不在/不确定)
思路:
和这题POJ 1182 食物链 并查集差不多。
划分为两个集合,给出D a b 说明a和b不在一个集合,那么就合并a和b+n,b和a+n。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN=200000+10; int fa[MAXN]; int find(int cur) { return cur==fa[cur]? cur: fa[cur]=find(fa[cur]); } void union_set(int a,int b) { int root_a=find(a); int root_b=find(b); if(root_a==root_b) return; fa[root_a]=root_b; } int main() { int T; scanf("%d",&T); while(T--) { int n,m; scanf("%d%d",&n,&m); int num=n*2; for(int i=1;i<=num;i++) fa[i]=i; char cmd[5]; int a,b; for(int i=0;i<m;i++) { scanf("%s %d%d",cmd,&a,&b); if(cmd[0]==‘A‘) { if(find(a)==find(b)) printf("In the same gang.\n"); else if(find(a)==find(b+n) || find(b)==find(a+n)) printf("In different gangs.\n"); else printf("Not sure yet.\n"); } else { union_set(a,b+n); union_set(a+n,b); } } } return 0; }
POJ 2236 Wireless Network ||POJ 1703 Find them, Catch them 并查集,古老的榕树,5-wow.com
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。