POJ3648：Wedding——题解（配2-SAT简易讲解）

http://poj.org/problem?id=3648

（在家，而且因为2-SAT写的不明不白的，所以这篇详细写）

题目大意：

有一对新人结婚，邀请了n-1 对夫妇去参加婚礼。婚礼上所有人要坐在一张很长的桌子的两边。所有的夫妇不能坐在同一边。还有m 对人，这对人不能同时坐在新郎一边，但可以同时坐在新娘这边或是分两边坐。

以这道题为2-SAT讲解模板题。

（请先了解2-SAT是干什么的再往下看）

首先判断：打眼一看一定是2-SAT。

然后建图，a到b表示如果选了a就一定选b的意思。

那么对于我们所给出的矛盾关系，发现a和b虽然不共边，但是a一定和b的另一半共边或着b一定和a的另一半共边。于是利用上面的定义加边。

这里假设k为妻子，k+n为丈夫。

有一个需要加的就是（0,0+n）需要加边（难点）

为什么呢？因为我们能够发现，只有新郎一边是不能冲突的，新娘一边随意，那么加上这条边时如果我们取了新娘就一定会取新郎而导致错误，所以程序一定会去选择新郎，由此我们得到了新郎那边的座次。在那之后全部相反就能获得新娘的座次了。

关键的2-SAT判冲突：

首先tarjan缩点，如果相互为夫妻的人在同一个强连通分量里就说明错误。

然后按照拓扑序我们有：（以（a，b）为一对冲突为例，取a表示a与新郎共边）

如果a所在的强连通分量（新图中的点）的拓扑序在b（非a）所在的强连通分量之后，则a为真。（显然取b就得取a而冲突，但是取a就可以不用取b避免冲突）

但是我们能够发现Tarjan 算法所求的强连通分量就是按拓扑序的逆序得出的，所以我们直接用编号来表示，并不需要真的去拓扑……

举个例子，比如这道题，明显i与i+n冲突，to[i]表示i缩点编号，那我们有：

to[i]<to[i+n]时取i，反之取i+n。

但是这是新郎侧编号，为了求新娘侧的人，我们把上面的条件颠倒一下即可。

（PS：此题输入有毒，如果不断RE请原模原样参照路由器的代码的读入写，你就明白数据有什么问题了）

#include<stack>

#include<cstdio>

#include<cstring>

#include<vector>

#include<iostream>

#include<algorithm>

using namespace std;const int N=;

const int M=;

struct node{

    int to;

    int nxt;

}edge[M*];

int head[N*],dfn[N*],low[N*],to[N*];

int n,m,t,l,cnt;

bool instack[N*];

stack<int>q;

inline void add(int u,int v){

    cnt++;

    edge[cnt].to=v;

    edge[cnt].nxt=head[u];

    head[u]=cnt;

    return;

}

inline int neg(int x){

    if(x<=n)return x+n;

    return x-n;

}

void tarjan(int u){

    t++;

    dfn[u]=t;

    low[u]=t;

    q.push(u);

    instack[u]=;

    for(int i=head[u];i!=;i=edge[i].nxt){

    int v=edge[i].to;

    if(!dfn[v]){

        tarjan(v);

        low[u]=min(low[u],low[v]);

    }else if(instack[v]){

        low[u]=min(low[u],dfn[v]);

    }

    }

    if(low[u]==dfn[u]){

    int v;

    l++;

    do{

        v=q.top();

        q.pop();

        instack[v]=;

        to[v]=l;

    }while(v!=u);

    }

    return;

}

inline void clr(){

    cnt=;t=;l=;

    memset(dfn,,sizeof(dfn));

    memset(head,,sizeof(head));

    return;

}

int main(){

    while(scanf("%d%d",&n,&m)!=EOF&&(n>||m>)){

    clr();

    for(int i=;i<=m;i++){

        int u,v;char a,b;

        scanf("%d%c %d%c",&u,&a,&v,&b);

        u++;v++;

        if(a=='h')u+=n;

        if(b=='h')v+=n;

        add(u,neg(v));

        add(v,neg(u));

    }

    add(,n+);

    for(int i=;i<=n*;i++){

        if(!dfn[i])tarjan(i);

    }

    bool flag=;

    for(int i=;i<=n;i++){

        if(to[i]==to[i+n]){

        flag=;

        break;

        }

    }

    if(!flag){

        printf("bad luck\n");

        continue;

    }

    for(int i=;i<=n;i++){

        printf("%d",i-);

        if(to[i]>to[i+n])printf("w ");

        else printf("h ");

    }

    printf("\n");

    }

    return ;

}

（敲了半个小时的同时搞懂了2-SAT，同时凌晨的城市真好看，好累……）

巴特西

POJ3648：Wedding——题解（配2-SAT简易讲解）

题目大意：

关键的2-SAT判冲突：

最新文章

热门文章