题意：给一堆离子，问能不能组成无限大的分子。
考虑朴素的\(n^2\) 暴力，即若两个离子能匹配，连一条边，判环。
发现本质不同的边非常少，所以将边转化为点考虑，即每个离子表示一组字符转换，这样图就很小了，暴力判即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 60 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; char s[N]; int f[N][N]; bool ok; bool v[N]; void dfs(int x,int s,bool pd) { if(ok)return ; if(x==s&&pd) { ok=1;return ; } if(v[x])return ; v[x]=1; for(int i=0;i<52;i++) if(f[x][i])dfs(i,s,1); } int main() { n=read(); while(n--) { scanf("%s",s+1); for(int i=1;i<=8;i+=2) if(s[i]!='0') { int u=(s[i]-'A')<<1; u^=(s[i+1]=='+'); for(int j=1;j<=8;j+=2) if(i!=j&&s[j]!='0') { int v=(s[j]-'A')<<1; v^=(s[j+1]=='-'); f[u][v]=1; } } } for(int i=0;i<52;i++) { memset(v,0,sizeof(v)); dfs(i,i,0); if(ok) { puts("unbounded"); return 0; } } puts("bounded"); } |
Comments | NOTHING