本文共 1291 字，大约阅读时间需要 4 分钟。
#include #include #include #include #include using namespace std;const int Maxn = 1e5+10;int mark[Maxn << 1];int s[Maxn * 2],top,tp;int head[Maxn*2];map mp;int x[Maxn * 2];struct { int v,next;}E[Maxn << 2];void init(){ memset(head,-1,sizeof(head)); memset(E,-1,sizeof(E)); tp = 0;}int n,m,a,b;void addedge(int u,int v){ E[tp].v = v; E[tp].next = head[u]; head[u] = tp++;}bool dfs(int x){ if(mark[x^1])return false; if(mark[x])return true; mark[x] = true; s[top++] = x; for(int i=head[x];i!=-1;i=E[i].next){ int v = E[i].v; if(!dfs(v))return false; } return true;}bool solve(){ for(int i=0;i 0)mark[s[--top]] = false; if(!dfs(i+1)) return false; } } } return true;}int main(){ init(); cin >> n >> a >> b; for(int i = 1;i<= n;i++){ scanf("%d",&x[i]); mp[x[i]] = i; } for(int i=1;i<=n;i++){ int val = x[i],s = i; s--; int t = mp[a - val];t--; if(!mp[a-val])addedge(2*s,2*s+1); else { addedge(2*s,2*t); addedge(2*t+1,2*s+1); } t=mp[b-val]; t--; if(!mp[b-val]) addedge(2*s+1,2*s); else{ addedge(2*s+1,2*t+1); addedge(2*t,2*s); } } if(!solve()){ puts("NO"); } else { printf("YES\n"); for(int i=0;i<2*n;i+=2){ if(i!=0) printf(" "); if(mark[i]) printf("0"); else printf("1"); } printf("\n"); }}
转载地址：http://ruiva.baihongyu.com/