HDU 1816， POJ 2723 Get Luffy Out
题目链接
题意：N串钥匙。每串2把，仅仅能选一把。然后有n个大门，每一个门有两个锁，开了一个就能通过，问选一些钥匙，最多能通过多少个门
思路：二分通过个数。然后对于钥匙建边至少一个不选，门建边至少一个选，然后2-sat搞一下就可以。
一開始是按每串钥匙为1个结点，但是后面发现数据有可能一把钥匙，出如今不同串（真是不合理），所以这个做法就跪了
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;const int MAXNODE = 2105;struct TwoSet {int n;vector<int> g[MAXNODE * 2];bool mark[MAXNODE * 2];int S[MAXNODE * 2], sn;void init(int tot) {n = tot * 2;for (int i = 0; i < n; i += 2) {g[i].clear();g[i^1].clear();}memset(mark, false, sizeof(mark));}void add_Edge(int u, int uval, int v, int vval) {u = u * 2 + uval;v = v * 2 + vval;g[u^1].push_back(v);g[v^1].push_back(u);}void delete_Edge(int u, int uval, int v, int vval) {u = u * 2 + uval;v = v * 2 + vval;g[u^1].pop_back();g[v^1].pop_back();}bool dfs(int u) {if (mark[u^1]) return false;if (mark[u]) return true;mark[u] = true;S[sn++] = u;for (int i = 0; i < g[u].size(); i++) {int v = g[u][i];if (!dfs(v)) return false;}return true;}bool solve() {for (int i = 0; i < n; i += 2) {if (!mark[i] && !mark[i + 1]) {sn = 0;if (!dfs(i)){for (int j = 0; j < sn; j++)mark[S[j]] = false;sn = 0;if (!dfs(i + 1)) return false;}}}return true;}
} gao;const int N = 2055;int n, m;
int x[N], y[N];
int k1[N], k2[N];bool judge(int d) {gao.init(2 * n);for (int i = 0; i < n; i++)gao.add_Edge(x[i], 0, y[i], 0);for (int i = 1; i <= d; i++)gao.add_Edge(k1[i], 1, k2[i], 1);return gao.solve();
}int main() {while (~scanf("%d%d", &n, &m) && n) {for (int i = 0; i < n; i++)scanf("%d%d", &x[i], &y[i]);for (int i = 1; i <= m; i++)scanf("%d%d", &k1[i], &k2[i]);int l = 0, r = m + 1;while (l < r) {int mid = (l + r) / 2;if (judge(mid)) l = mid + 1;else r = mid;}printf("%d\n", l - 1);}return 0;
}
