题目大意：有N串钥匙，M对锁。每串钥匙仅仅能选择当中一把。怎样选择，才干使开的锁达到最大(锁仅仅能按顺序一对一对开。仅仅要开了当中一个锁就可以)
解题思路：这题跟
这题的限制比較简单。都是二选一，2-SAT的裸题，仅仅只是加了二分而已 附上#include#include #include #include using namespace std;#define N 4010struct Pair{ int x, y;}P[N];int lock1[N], lock2[N], S[N];bool mark[N];int top, n, m;vector G[N];void init() { for (int i = 0; i < n; i++) { scanf("%d%d", &P[i].x, &P[i].y); } for (int i = 1; i <= m; i++) scanf("%d%d", &lock1[i], &lock2[i]);}void AddEdge(int x, int valx, int y, int valy) { x = x * 2 + valx; y = y * 2 + valy; G[x ^ 1].push_back(y); G[y ^ 1].push_back(x);}bool dfs(int u) { if (mark[u ^ 1]) return false; if (mark[u]) return true; mark[u] = true; S[++top] = u; for (int i = 0; i < G[u].size(); i++) if (!dfs(G[u][i])) return false; return true;}bool judge(int mid) { for (int i = 0; i < 4 * n; i++) G[i].clear(); for (int i = 0; i < n; i++) AddEdge(P[i].x, 0, P[i].y, 0); for (int i = 1; i <= mid; i++) AddEdge(lock1[i], 1, lock2[i], 1); memset(mark, 0, sizeof(mark)); for (int i = 0; i < 4 * n; i++) { if (!mark[i] && !mark[i ^ 1]) { top = 0; if (!dfs(i)) { while (top) mark[S[top--]] = false; if (!dfs(i ^ 1)) return false; } } } return true;}void solve() { int l = 1, r = m, mid; while (l <= r) { mid = (l + r) / 2; if (judge(mid)) l = mid + 1; else r = mid - 1; } printf("%d\n", l - 1);}int main() { while (scanf("%d%d", &n, &m) != EOF && n + m) { init(); solve(); } return 0;}