题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2199
使用Samsung Dex写的第一份代码，体验还不错。。。
按照题意建出2-sat的图，然后从每个点尝试跑，成功就记录一下
|
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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<bits/stdc++.h> #define pb push_back #define maxn 1010 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct two_sat{ int n; bool mark[maxn*2]; vector<int>go[maxn*2],stk; void init(int x){ n=x; for(int i=0; i<2*n; i++)go[i].clear(); memset(mark,0,sizeof(mark)); } void add_edge(int x,int xx,int y,int yy){ x=x*2+xx; y=y*2+yy; go[x^1].pb(y); go[y^1].pb(x); } bool dfs(int x){ if(mark[x^1])return false; if(mark[x])return true; mark[x]=true; stk.pb(x); for(int i=0; i<go[x].size(); i++)if(!dfs(go[x][i]))return false; return true; } bool solve(int x){ stk.clear(); if(!dfs(x))return false; for(int i=0; i<n*2; i+=2){ if(!mark[i] && !mark[i+1]){ stk.clear(); if(dfs(i))continue; for(int j=0; j<stk.size(); j++)mark[stk[j]]=false; stk.clear(); if(dfs(i+1))continue; return false; } } return true; } }TS; bool flag,can[maxn*2]; int main(){ int n=rd(),m=rd(); TS.init(n); for(int i=0; i<m; i++){ int a1,a2; char c1,c2; a1=rd(),c1=getchar();a1--; while(c1!='Y' && c1!='N')c1=getchar(); a2=rd(),c2=getchar();a2--; while(c2!='Y' && c2!='N')c2=getchar(); TS.add_edge(a1,c1=='N',a2,c2=='N'); } for(int i=0; i<n; i++){ memset(TS.mark,0,sizeof(TS.mark)); TS.mark[2*i]=true; if(TS.solve(2*i))can[2*i]=true,flag=true; memset(TS.mark,0,sizeof(TS.mark)); TS.mark[2*i+1]=true; if(TS.solve(2*i+1))can[2*i+1]=true,flag=true; } if(!flag)puts("IMPOSSIBLE"); else{ for(int i=0; i<n; i++){ if(can[2*i] && can[2*i+1])putchar('?'); else if(can[2*i])putchar('Y'); else putchar('N'); } } return 0; } |