自动搬运

查看原文

来自洛谷，原作者为

	Ymy1201 一只正在摸鱼的蒟蒻||100%回关||忘关私我||暑假后小学六年级||玩火影Q区44439234846（是个小白）阿玛特拉斯

搬运于2025-08-24 22:59:40，当前版本为作者最后更新于2025-08-16 12:41:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

吐槽：我竟然是第一篇题解。

P10615 [ICPC 2013 WF] Self-Assembly

题目大意

给定一串分子，分子是正方形，问能否用这些分子拼成一个无限大的结构。

分析

其实这道题就是一道检测图有没有环的问题，如果有环就输出unbounded，没有就输出bounded。

将每个分子（如A-、A+、B+，但00不算）看作图的节点，将两个互相兼容的分子连上一条边，最后在检测有没有环就行了。

上代码！！！

#include<bits/stdc++.h>
using namespace std;
int n;
string s[40001];
unordered_map<string,vector<string> >m;
unordered_set<string>m2;
unordered_map<string,int>vis;
bool dfs(string x) {
	vis[x]=1;
	for(string i:m[x]) {
		if(vis[i]==1)return 1;
		if(!vis[i]&&dfs(i))return 1;
	}
	vis[x]=2;
	return 0;
}
int main() {
//	freopen("a.in","r",stdin);
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		cin>>s[i];
		for(int j=0; j<4; j++) {
			string a=s[i].substr(j<<1,2);
			if(a=="00")continue;
			for(int k=0; k<4; k++) {
				if(j==k)continue;
				string b=s[i].substr(k<<1,2);
				if(b=="00")continue;
				string c=b[1]=='+'?string(1,b[0])+"-":string(1,b[0])+"+";
				m[a].push_back(c);
				m2.insert(a);
				m2.insert(c);
			}
		}
	}
	for(string i:m2)
		if(!vis[i]&&dfs(i))return puts("unbounded"),0;
	puts("bounded");
	return 0;
}

点个赞再走呗？