题解：P10615 [ICPC 2013 WF] Self-Assembly

· · 题解

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

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;
}

点个赞再走呗？