PKU 2372 Get Luffy Out
时间:2010-10-11 来源:晓天
* File: PKU 2372 Get Luffy Out
* Author: xiaotian @ hnu
* Created on 2010年10月11日, 上午9:52
* 题解:二分 + 2-sat验证
* 建图:对于每一对钥匙(X,Y),如果使用X就不能使用Y,故添加边(X,Y'),(Y,X').
* 对于每一扇名门,只需打开其中一把锁即可,故添加边(X',Y),(Y',X).

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
#define N 4508 /*顶点总数,包括拆点以后的*/
#define M 2050
#define inf 0x7ffffff
struct node {
int a, b;
node(int aa = 0, int bb = 0) : a(aa), b(bb) {}
};
node key[M / 2];
node door[M];
vector<int>g[N]; /*邻接表*/
int n, m; /*顶点数,边数*/
int id[N], pre[N], low[N], s[N], stop, cnt, scnt;
void tarjan(int v, int n) { /*求强连通分量,vertex: 0 ~ n-1*/
int t, minc = low[v] = pre[v] = cnt++;
s[stop++] = v;
for (int i = 0; i < g[v].size(); i++) {
if (-1 == pre[g[v][i]]) tarjan(g[v][i], n);
if (low[g[v][i]] < minc) minc = low[g[v][i]];
}
if (minc < low[v]) { low[v] = minc; return; }
do { id[t = s[--stop]] = scnt; low[t] = n; } while (t != v);
++scnt; /*联通分量个数*/
}
bool _2sat() {
stop = cnt = scnt = 0;
memset(pre, -1, sizeof (pre));
for (int i = 0; i < n; ++i) if (-1 == pre[i]) tarjan(i, n);
n /= 2;
for (int i = 0; i < n; i++) if (id[i] == id[i + n]) return 0;
return 1;
}
void add(int a, int b) {
g[a].push_back(b);
}
void build(int mid) {
int a, b;
int k = n * 2;
for (int i = 0; i < k; i++) g[i].clear(), g[i + k].clear();
for (int i = 0; i < n; i++) {
a = key[i].a,b = key[i].b;
add(a, b + k);
add(b, a + k);
}
for (int i = 0; i < mid; i++) {
a = door[i].a, b = door[i].b;
add(a + k, b);
add(b + k, a);
}
n = k + k;
}
void read() {
int a, b;
for (int i = 0; i < n; key[i] = node(a, b), i++)
scanf("%d%d", &a, &b);
for (int i = 0; i < m; door[i] = node(a, b), i++)
scanf("%d%d", &a, &b);
}
int main() {
while (scanf("%d%d", &n, &m) != EOF) {
if (n == 0 && m == 0) return 0;
read();
int l = 0, r = m,mid,ans;
while (l <= r) {
mid = (r + l) / 2;
build(mid);
if (_2sat())
{
ans=mid;
l = mid + 1;
}
else r = mid - 1;
n /= 2;
}
printf("%d\n", ans);
}
return 0;
}
相关阅读 更多 +