POJ 2723 2分+ 2-sat 判定

2012-08-01

POJ 2723 二分+ 2-sat 判定此题的题意很简单，有一些个门，还有2 * n个钥匙分成了n组，每组里有两把钥匙，并

POJ 2723 二分+ 2-sat 判定

此题的题意很简单，有一些个门，还有2 * n个钥匙分成了n组，每组里有两把钥匙，并且每组中只能使用一把钥匙，然后每个门有两把锁，分别对应着钥匙，两个锁只要任意开一个门就会打开，并且，要打开一个门，必须保证他序号之前的所有门都打开了，类似于一关一关的往里闯

然后思路的话，由于是必须顺序的开门，所以可以进行二分枚举答案，如果枚举的数为m, 则我们要判定的就是1~m的门是否能被打开，就要用2-sat建图判定了

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>#define MAXN 5005#define MAXM 50005#define INF 1000000000using namespace std;struct Edge{    int v, next;}edge[MAXM];int n, m, e;int top, scc, index;int low[MAXN], dfn[MAXN], instack[MAXN];int head[MAXN], st[MAXN], fa[MAXN];int a[MAXN], b[MAXN], hash[MAXN];int x[MAXN], y[MAXN];void init(){    top = scc = index = e = 0;    memset(head, -1, sizeof(head));    memset(dfn, 0, sizeof(dfn));    memset(instack, 0, sizeof(instack));}void insert(int x, int y){    edge[e].v = y;    edge[e].next = head[x];    head[x] = e++;}void tarjan(int u){    low[u] = dfn[u] = ++index;    instack[u] = 1;    st[++top] = u;    int v;    for(int i = head[u]; i != -1; i = edge[i].next)    {        v = edge[i].v;        if(!dfn[v])        {            tarjan(v);            low[u] = min(low[u], low[v]);        }        else if(instack[v]) low[u] = min(low[u], dfn[v]);    }    if(dfn[u] == low[u])    {        scc++;        do        {            v = st[top--];            instack[v] = 0;            fa[v] = scc;        }while(v != u);    }}bool check(int n){    for(int i = 1; i <= n; i++)        if(fa[i] == fa[i + n]) return false;    return true;}void build(int bound){    init();    for(int i = 1; i <= n; i++)    {        insert(a[i], b[i] + 2 * n);        insert(b[i], a[i] + 2 * n);    }    for(int i = 1; i <= bound; i++)    {        insert(x[i] + 2 * n, y[i]);        insert(y[i] + 2 * n, x[i]);    }    for(int i = 1; i <= 2 * n; i++)        if(!dfn[i]) tarjan(i);}void solve(){    int ans = 0;    int low = 0, high = m;    while(low <= high)    {        int mid = (low + high) >> 1;        build(mid);        if(check(n * 2)) ans = max(ans, mid), low = mid + 1;        else high = mid - 1;    }    printf("%d\n", ans);}int main(){    while(scanf("%d%d", &n, &m) != EOF)    {        if(n == 0 && m == 0) break;        for(int i = 1; i <= n; i++)        {            scanf("%d%d", &a[i], &b[i]);            a[i]++; b[i]++;        }        for(int i = 1; i <= m; i++)        {            scanf("%d%d", &x[i], &y[i]);            x[i]++; y[i]++;        }        solve();    }    return 0;}

热点排行

编程

POJ 2723 2分+ 2-sat 判定