POJ 2-sat六题之五
http://blog.sina.com.cn/s/blog_64675f540100k2rh.html
题目描述：
有2n把钥匙，分成2组，给你每组的钥匙信息，并且每组的钥匙只能用一个。
有m个门，每个门有2个锁，只要打开一个锁这个门就开了。（顺序遇见m个门）
问你最多能够打开多少个门。
解题报告：
2n个钥匙，定义4n个节点，1~2n中的i表示用第i个钥匙。 2n+1~4n中的j， 表示不用j - 2n号钥匙。
那么对与给你的n组钥匙的每一组a和b。
有边<a, b + 2n> 和 <b, a + 2n>（只能选一个钥匙）
对于给你的m个门的两个锁a和b
有边<a + 2n, b> <b + 2n, a> 至少选一个。
然后枚举1~m个门，看看最后能到第几个门能够满足条件（数据比较少，不用二分也能过）
// File Name: 2723.cpp // Author: zlbing // Created Time: 2013/2/4 23:02:01 #include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> using namespace std; const int MAXN=3e3; struct TwoSAT{ int n; vector<int>G[MAXN*2]; bool mark[MAXN*2]; stack<int>S; bool dfs(int x) { if(mark[x^1])return false; if(mark[x])return true; mark[x]=true; S.push(x); for(int i=0;i<G[x].size();i++) { int v=G[x][i]; if(!dfs(v))return false; } return true; } void init(int _n) { n=_n; for(int i=0;i<2*n;i++) G[i].clear(); memset(mark,0,sizeof(mark)); } void add_clause(int x,int y) { G[x].push_back(y); } bool solve() { for(int i=0;i<2*n;i=i+2) { if(!mark[i]&&!mark[i+1]){ while(!S.empty()) { S.pop(); } if(!dfs(i)) { while(!S.empty()) { mark[S.top()]=false; S.pop(); } if(!dfs(i+1))return false; } } } // for(int i=0;i<2*n;i++) // if(mark[i])printf("%d ",T[i/2][i%2]); // printf("\n"); return true; } }; int main(){ TwoSAT solver; int n,m; while(~scanf("%d%d",&n,&m)) { if(n==0&&m==0) break; solver.init(2*n); int a,b; for(int i=0;i<n;i++) { scanf("%d%d",&a,&b); solver.add_clause(2*a,2*b+1); solver.add_clause(2*b,2*a+1); } int ans=0; bool flag=true; for(int i=0;i<m;i++) { scanf("%d%d",&a,&b); if(flag){ solver.add_clause(2*a+1,2*b); solver.add_clause(2*b+1,2*a); //一开始mark没初始化，导致一直错误。每次重新算时应该初始化下 memset(solver.mark,0,sizeof(solver.mark)); if(solver.solve()) ans++; else flag=false; } } printf("%d\n",ans); } return 0; }