首页 > 代码库 > 【图论】Self-Assembly(6-19)
【图论】Self-Assembly(6-19)
[UVA1572]Self-Assembly
算法入门经典第6章6-19(P172)
题目大意:有一些正方形,每条边上都有A-~Z- A+~Z+的编号,或者00,A+的边可以拼A-,反之亦然。00的边什么都不能拼。问是否能无限去拼。
试题分析:直接做没有头绪,但是发现可以旋转和翻转,这样就可以从任意正方形喀什了。我们将A-~Z+这52种连有向边,最后判断有没有有向环即可。
#include<iostream>#include<cstring>#include<cstdio>#include<vector>#include<queue>#include<stack>#include<algorithm>using namespace std;inline int read(){ int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f;}const int MAXN=100001;const int INF=999999;int N,M;int T;char a[5],b[5];vector<int> vec[101];int vis[1001];int Hash(int k){ return (a[k]-‘A‘+1)*2-(b[k]==‘-‘?1:0);}bool dfs(int x){ vis[x]=-1; if(x%2==0) x--; else x++; for(int i=0;i<vec[x].size();i++){ int to=vec[x][i]; if(vis[to]==-1) return true; else if(!vis[to]&&dfs(to)) return true; } if(x%2==0) x--; else x++; vis[x]=1; return false;}int main(){ while(scanf("%d",&N)!=EOF){ for(int i=1;i<=70;i++) vec[i].clear(); for(int i=1;i<=N;i++){ for(int j=1;j<=4;j++) cin>>a[j]>>b[j]; for(int j=1;j<=4;j++){ if(a[j]==‘0‘) continue; for(int k=j+1;k<=4;k++){ if(a[k]==‘0‘) continue; int at=Hash(j); int bt=Hash(k); vec[at].push_back(bt); vec[bt].push_back(at); } } } memset(vis,0,sizeof(vis)); bool flag=false; for(int i=1;i<=52;i++){ if(!vis[i]&&dfs(i)) {flag=true; break;} } if(flag){ puts("unbounded"); } else puts("bounded"); }}
【图论】Self-Assembly(6-19)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。