文章详情

  • 游戏榜单
  • 软件榜单
关闭导航
热搜榜
热门下载
热门标签
php爱好者> php文档>PKU 2372 Get Luffy Out

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).

 

Code for PKU 2372
#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;
}

 

相关阅读 更多 +
排行榜 更多 +
PvZ戴夫的时空冒险重置

PvZ戴夫的时空冒险重置

策略塔防 下载
PVZTV雪版阳光加50

PVZTV雪版阳光加50

策略塔防 下载
双刃战士雪姐

双刃战士雪姐

冒险解谜 下载