首页 > 代码库 > 【图论】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)