相关链接
题目传送门:http://codeforces.com/contest/782/problem/D
吐槽
为什么题面这么难懂啊?!
感觉出题人的英文比我好不到哪里去啊?!
差一点写成二分图了,还好室友嘈代码难写的时候多问了一句 _(:з」∠)_
解题报告
我们发现每个人只有两个状态
于是我们撸一发2-SAT就可以A辣!
Code
2-SAT判定有没有解是可以做到$O(m)$的,写个强连通就可以了
不过我这份代码是$O(m^2)$的啊!
为什么不会T?我的$m$是$O(n^2)$的啊
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 5000; const int M = 5000009; int n,que[N],cnt,head[N],to[M],nxt[M],mark[N]; char pat[2][100]; struct Data{ char p[4]; inline bool operator < (const Data &B) const { for (int i=0;i<3;i++) { if (p[i] < B.p[i]) return 1; else if (p[i] > B.p[i]) return 0; } return 0; } inline bool operator == (const Data &B) const { return !(*this < B) && !(B < *this); } }c1[N],c2[N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void Add_Edge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; } inline int id(int w, int t) { return (w-1)*2 + t + 1; } bool DFS(int w) { if (mark[w]) return true; if (mark[w^1]) return false; mark[w] = 1; que[++cnt] = w; for (int i=head[w];i;i=nxt[i]) if (!DFS(to[i])) return false; return true; } inline bool judge(){ for (int i=2,lim=id(n,2);i<=lim;i+=2) if (!mark[i] && !mark[i+1]) { cnt = 0; if (DFS(i)) continue; for (int j=1;j<=cnt;j++) mark[que[j]] = 0; cnt = 0; if (!DFS(i+1)) return false; } return true; } int main() { n = read(); for (int i=1;i<=n;i++) { scanf("%s%s",pat[0],pat[1]); Data a; a.p[3] = 0; a.p[0] = pat[0][0]; a.p[1] = pat[0][1]; a.p[2] = pat[0][2]; Data b; b.p[3] = 0; b.p[0] = pat[0][0]; b.p[1] = pat[0][1]; b.p[2] = pat[1][0]; c1[i] = a; c2[i] = b; } for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if (i == j) continue; if (c1[i] == c1[j]) Add_Edge(id(i, 2), id(j, 2)); if (c1[i] == c1[j]) Add_Edge(id(i, 1), id(j, 2)); if (c1[i] == c2[j]) Add_Edge(id(i, 1), id(j, 1)); if (c2[i] == c1[j]) Add_Edge(id(i, 2), id(j, 2)); if (c2[i] == c2[j]) Add_Edge(id(i, 2), id(j, 1)); } } if (!judge()) puts("NO"); else { puts("YES"); for (int i=1;i<=n;i++) { if (mark[id(i, 1)]) printf("%s\n",c1[i].p); else printf("%s\n",c2[i].p); } } return 0; }
—————————— UPD 2017.3.27 ——————————
今天才知道输出一组可行解也是可以$O(m)$的
大概就是搞一发Tarjan,然后在拓扑图上按拓扑逆序染色