P3007 [USACO11JAN]大陆议会The Continental Cowngress
洛谷
GDOI
首先,按照2−SAT问题的套路,我们要把这个转化成依赖性问题
又发现一只奶牛刚好投两次票,所以只要不满足奶牛的其中一次投票,就要满足另一次,这样就转化成了依赖性问题。
但是,这道题还要输出"?",怎么搞
再看一眼数据范围1≤N≤1000,这样小的数据范围,暴力都能过。
于是不妨从两个相对的节点bfs一遍,如果他们两个都没有矛盾,那么输出?,如果一个有矛盾,那么输出Y/N,如果都有矛盾,那么输出IMPOSSIBLE。
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
| #include <bits/stdc++.h> #define MAXN 4005 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<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } vector<int>G[MAXN]; inline void AddEdge(int u,int v){ G[u].push_back(v); } int vis[MAXN],n,m; inline int Other(int u){ if (u<=n) return u+n; else return u-n; } inline bool bfs(int s){ memset(vis,0,sizeof(vis)); queue<int>Q; Q.push(s); while (Q.size()){ int u=Q.front();Q.pop(); vis[u]=true; if (vis[Other(u)]) return false; for (register int i=0;i<G[u].size();++i){ int v=G[u][i]; if (!vis[v]) Q.push(v); } } return true; } inline char gc(){ char ch=getchar(); while (ch!='Y'&&ch!='N') ch=getchar(); return ch=='Y'; } int main(){ n=read(),m=read(); for (register int i=1;i<=m;++i){ int u=read(),f1=gc(),v=read(),f2=gc(); AddEdge(u+(!f1)*n,v+f2*n); AddEdge(v+(!f2)*n,u+f1*n); } string Ans=""; for (register int i=1;i<=n;++i){ bool True=bfs(i),False=bfs(Other(i)); if (!True&&!False){ puts("IMPOSSIBLE"); return 0; } else if (True&&!False){ Ans+='N'; } else if (False&&!True){ Ans+='Y'; } else { Ans+='?'; } } cout<<Ans<<endl; }
|