POJ 2723 二分 + 2-SAT

题意

传送门 POJ 2723

题解

定义布尔变量 $$x_i为真?使用钥匙i$$ 对于成对的钥匙，相互之间至多能使用一把，则有 $?x_i\vee ?x_j$ 为真；对于门上的一对所，至少需要打开一个，则有 $x_i\vee x_j$ 为真。那么能打开到第 $k$ 道门说明存在存在一组布尔变量使得布尔方程值为真，是一个 $2?SAT$ 问题。

若至多可打开 $k$ 道门，则一定可以打开 $k^{\prime }<k$ 道门，二分答案即可，复杂度 $O(NlogN)$。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define maxn (1 << 12) + 5
int n, m, n2, cmp[maxn], key[maxn], door[maxn];
bool used[maxn];
vector<int> G[maxn], rG[maxn], vs;void add_edge(int u, int v)
{
    G[u].push_back(v);rG[v].push_back(u);
}void dfs(int v)
{
    used[v] = 1;for (int i = 0; i < G[v].size(); i++){
    int u = G[v][i];if (!used[u]){
    dfs(u);}}vs.push_back(v);
}void rdfs(int v, int k)
{
    used[v] = 1, cmp[v] = k;for (int i = 0; i < rG[v].size(); i++){
    int u = rG[v][i];if (!used[u]){
    rdfs(u, k);}}
}int scc(int n)
{
    vs.clear();memset(used, 0, sizeof(used));for (int v = 0; v < n; v++){
    if (!used[v]){
    dfs(v);}}memset(used, 0, sizeof(used));int k = 0;for (int i = vs.size() - 1; i >= 0; i--){
    int v = vs[i];if (!used[v]){
    rdfs(v, k++);}}return k;
}bool judge(int k)
{
    for (int i = 0; i < (n2 << 1); i++){
    G[i].clear();rG[i].clear();}for (int i = 0; i < n; i++){
    int a = key[i], b = key[n + i];add_edge(a, n2 + b);add_edge(b, n2 + a);}for (int i = 0; i < k; i++){
    int a = door[i], b = door[m + i];add_edge(n2 + a, b);add_edge(n2 + b, a);}scc(n2 << 1);for (int i = 0; i < n2; i++){
    if (cmp[i] == cmp[i + n2]){
    return 0;}}return 1;
}int main()
{
    while (~scanf("%d%d", &n, &m) && (n | m)){
    n2 = n << 1;for (int i = 0; i < n; i++){
    scanf("%d%d", key + i, key + n + i);}for (int i = 0; i < m; i++){
    scanf("%d%d", door + i, door + m + i);}int lb = 0, ub = m + 1;while (ub - lb > 1){
    int mid = (lb + ub) >> 1;if (judge(mid))lb = mid;elseub = mid;}printf("%d\n", lb);}return 0;
}