2-SAT 例题泛做

21 Oct 2016

好久不写博客，这段时间实在是有点忙…写的题都没空发上来，马上就是区域赛了，现在一直在攻图论（毕竟软肋），希望能在区域赛有所帮助。

HDU 3062 Party

题目链接

Party

题目大意

现有n对夫妻和一个聚会，聚会要求n个人参加，每对夫妻需要出一个人参加聚会，但是某些人之间又有矛盾，现在给出矛盾关系，让你求是否可能举办Party 。

题解

2-SAT模板题，相当于有n个点，某两个点的状态之间是矛盾的。于是我们可以据此建边，然后跑一遍 $tarjan$ 就可以了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define maxn 1005

using namespace std;

int n,m,a1,a2,c1,c2,pre[maxn*2],cnt,dfn[maxn*2],low[maxn*2],p;
int sta[maxn*2],h,Cnt,scc[maxn*2];
struct edge
{
    int u,v,next;
};
edge e[maxn*maxn*2];
bool vis[maxn*2];
vector<int> v[maxn*2];


void addedge(int u,int v)
{
    e[cnt].u=u; e[cnt].v=v; e[cnt].next=pre[u];
    pre[u]=cnt++;
}

void tarjan(int u)
{
    low[u]=dfn[u]=p++;
    vis[u]=1;
    sta[h++]=u;
    for (int i=pre[u];i!=-1;i=e[i].next)
    {
        int v=e[i].v;
        if (!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if (vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if (low[u]==dfn[u])
    {
        int c=2*n;
        while (c!=u)
        {
            c=sta[--h]; scc[c]=Cnt;
            vis[c]=0; sta[h]=0;
            v[Cnt].push_back(c);
        }
        Cnt++;
    }
}

int main()
{
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        memset(pre,-1,sizeof(pre));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low)); cnt=0;
        memset(vis,0,sizeof(vis));
        memset(scc,0,sizeof(scc)); Cnt=0;
        h=0;

        for (int i=0;i<m;i++)
        {
            scanf("%d%d%d%d",&a1,&a2,&c1,&c2);
            addedge(a1*2+c1,(a2*2+c2)^1 );
            addedge(a2*2+c2,(a1*2+c1)^1 );
        }
        p=1;
        for (int i=0;i<2*n;i++) v[i].clear();
        for (int i=0;i<2*n;i++) if (!dfn[i]) tarjan(i);
        bool f=0;
        for (int i=0;i<n*2;i+=2) if (scc[i]==scc[i+1])
        {
            f=1; break;
        }
        if (f) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

POJ 3648 Wedding

题目链接

Wedding

题目大意&题解

这一题题目意思比较奇怪…看了别人的博客才看懂题目是什么意思…大概就是说有2n个人要坐在新娘的对面，但是这些人里面不能有夫妻，也不能有搞基的…我们按照题目给的关系建图就可以了，只不过这一题要输出解。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#define maxn 1005

using namespace std;

char a,b;
int n,m,x1,x2,p,cnt,pre[maxn<<1],dfn[maxn*2],low[maxn*2];
int sta[maxn*2],h,de[maxn*2],num,scc[maxn*2],opp[maxn*2],col[maxn<<1];
struct edge
{
    int u,v,next;
};
edge e[maxn*maxn*2];
bool vis[maxn*2];
vector<int> G[maxn*2];

void addedge(int u,int v)
{
    e[cnt].u=u; e[cnt].v=v; e[cnt].next=pre[u];
    pre[u]=cnt++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=p++;
    vis[u]=1; sta[h++]=u;

    for (int i=pre[u];i!=-1;i=e[i].next)
    {
        int v=e[i].v;
        if (!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if (vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if (low[u]==dfn[u])
    {
        int v;
        do
        {
            v=sta[--h];
            vis[v]=0;
            scc[v]=num;
        }
        while (v!=u);
        num++;
    }
}

bool Check()
{
    for (int i=0;i<2*n;i++) if (!dfn[i]) tarjan(i);
    for (int i=0;i<2*n;i+=2) if (scc[i]==scc[i+1]) return 0;
    for (int i=0;i<2*n;i+=2) opp[scc[i]]=scc[i+1],opp[scc[i+1]]=scc[i];
    return 1;
}

void buildmap()
{
    for (int i=0;i<num;i++) G[i].clear();
    for (int i=0;i<cnt;i++)
    {
        int u,v;
        u=e[i].u; v=e[i].v;
        if (scc[u]!=scc[v])
        {
            G[scc[v]].push_back(scc[u]);
            de[scc[u]]++;
        }
    }
}

void solve()
{
    queue<int> q;
    memset(col,0,sizeof(col));
    for (int i=0;i<num;i++) if (!de[i]) q.push(i);

    while (!q.empty())
    {
        int v=q.front(); q.pop();
        if (!col[v])
        { col[v]=1; col[opp[v]]=2; }
        for (int i=0;i<G[v].size();i++)
        {
            de[G[v][i]]--;
            if (de[G[v][i]]==0) q.push(G[v][i]);
        }
    }
}

int main()
{
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        memset(pre,-1,sizeof(pre));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        cnt=0; p=1;

        for (int i=0;i<m;i++)
        {
            scanf("%d%c %d%c",&x1,&a,&x2,&b);
            if (a=='h' && b=='h') addedge(x1*2+1,x2*2),addedge(x2*2+1,x1*2);
            else if (a=='h' && b=='w') addedge(x1*2+1,x2*2+1),addedge(x2*2,x1*2);
            else if (a=='w' && b=='h') addedge(x1*2,x2*2),addedge(x2*2+1,x1*2+1);
            else addedge(x1*2,x2*2+1),addedge(x2*2,x1*2+1);
        }
        addedge(0,1);
        if (Check())
        {
            buildmap();
            solve();
            for (int i=2;i<2*n;i++) if (col[scc[i]]==1)
            {
                if (i&1) printf("%dw ",i/2);
                else printf("%dh ",i/2);
            }
        }
        else printf("bad luck\n");
    }
    return 0;
}

POJ 3207 Ikki’s Story IV - Panda’s Trick

题目链接

Ikki’s Story IV - Panda’s Trick

题目大意&题解

这个题比较有意思一点。说是n个点，标号从0到n，现在有若干条线段，可以从园内连也可以从圆外连，每条线段的端点都是这n个点中的某两个，现在告诉你一个点不会成为两个线段的端点，问你这若干条线段是否会相交。

可以先将线段按照右端点排序，然后判断两条线段之间是否会冲突（冲突的意思就是比如一条线段从圆内连，另外一条线段就必须要从圆外面连），我们根据冲突建边之后，跑一遍 $tarjan$ 就可以了。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define maxn 1005
#define maxm 505

using namespace std;

int n,m,pre[maxn<<1],cnt,dfn[maxn<<1],low[maxn<<1],p;
int sta[maxn<<1],h,scc[maxn<<1],num;
bool vis[maxn*2];
struct line
{
    int l,r;
    bool operator <(const line &x) const
    {
        if (r!=x.r)return r<x.r;
        return l<x.l;
    }
};
line L[maxm];
struct edge
{
    int u,v,next;
};
edge e[maxm*maxm];

void addedge(int u,int v)
{
    e[cnt].u=u; e[cnt].v=v;
    e[cnt].next=pre[u]; pre[u]=cnt++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=p++;
    vis[u]=1;
    sta[h++]=u;

    for (int i=pre[u];i!=-1;i=e[i].next)
    {
        int v=e[i].v;
        if (!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if (vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u])
    {
        int c;
        do
        {
            c=sta[--h];
            vis[c]=0;
            scc[c]=num;
        }
        while (c!=u) ;
        num++;
    }
}

int main()
{
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        memset(pre,-1,sizeof(pre));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(sta,0,sizeof(sta)); h=0;
        memset(scc,0,sizeof(scc));
        memset(vis,0,sizeof(vis));
        int l,r; p=1; cnt=0;

        for (int i=0;i<m;i++) scanf("%d%d",&L[i].l,&L[i].r);
        sort(L,L+m);
        for (int i=m-1;i>=0;i--)
            for (int j=i-1;j>=0;j--)
            if (L[j].r>L[i].l && L[j].l<L[i].l)
            {
                addedge(L[j].l*2,L[i].l*2+1); addedge(L[j].l*2+1,L[i].l*2);
                addedge(L[i].l*2+1,L[j].l*2); addedge(L[i].l*2,L[j].l*2+1);
            }
        bool f=0;
        for (int i=0;i<2*n;i++) if (!dfn[i]) tarjan(i);
        for (int i=0;i<2*n;i+=2) if (scc[i]==scc[i+1])
        {
            f=1;
            break;
        }
        if (f) printf("the evil panda is lying again\n");
        else printf("panda is telling the truth...\n");
    }
    return 0;
}

POJ 3678 Katu Puzzle

题目链接

Katu Puzzle

题目大意&题解

最裸的2-SAT了，n个值，告诉你每两个值之间的关系 $(or,and,xor == 0/1)$ ，现在让你求是否合法。

直接建立矛盾关系在图上跑一遍就行啦~

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 1000
#define maxm 1000005

using namespace std;

int n,m,cnt,pre[maxn<<1],dfn[maxn<<1],low[maxn<<1];
int scc[maxn<<1],p,sta[maxn<<1],h,num;
struct edge
{
    int u,v,next;
};
edge e[maxm];
bool vis[maxn<<1];

void addedge(int u,int v)
{
    e[cnt].u=u; e[cnt].v=v;
    e[cnt].next=pre[u]; pre[u]=cnt++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=p++;
    vis[u]=1; sta[h++]=u;

    for (int i=pre[u];i!=-1;i=e[i].next)
    {
        int v=e[i].v;
        if (!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if (vis[v]) low[u]=min(dfn[v],low[u]);
    }
    if (dfn[u]==low[u])
    {
        int c;
        do
        {
            c=sta[--h];
            vis[c]=0;
            scc[c]=num;
        }
        while (c!=u);
        num++;
    }
}

int main()
{
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        memset(pre,-1,sizeof(pre)); cnt=0;
        memset(dfn,0,sizeof(dfn)); p=1;
        memset(low,0,sizeof(low)); h=0;
        memset(scc,0,sizeof(scc)); num=0;
        int a,b,c; char s[5];

        for (int i=0;i<m;i++)
        {
            scanf("%d%d%d%s",&a,&b,&c,s);
            if (s[0]=='A')
            {
                if (c) addedge(a*2+1,a*2),addedge(b*2+1,b*2);
                else addedge(a*2,b*2+1),addedge(b*2,a*2+1);
            }
            else if (s[0]=='O')
            {
                if (c) addedge(a*2+1,b*2),addedge(b*2+1,a*2);
                else addedge(a*2,a*2+1),addedge(b*2,b*2+1);
            }
            else if (s[0]=='X')
            {
                if (c)
                {
                    addedge(a*2,b*2+1); addedge(b*2,a*2+1);
                    addedge(b*2+1,a*2); addedge(a*2+1,b*2);
                }
                else
                {
                    addedge(a*2,b*2); addedge(a*2+1,b*2+1);
                    addedge(b*2,a*2); addedge(b*2+1,a*2+1);
                }
            }
        }
        bool f=0;
        for (int i=0;i<2*n;i++) if (!dfn[i]) tarjan(i);
        for (int i=0;i<2*n;i+=2) if (scc[i]==scc[i+1])
        {
            f=1;
            break ;
        }
        if (f) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

HDU 4421 Bit Magic

题目链接

Bit Magic

题目大意&题解

这一题就是上一题的升级版，他现在把1位关系变成了32位关系，让你求是否可行。

一样的做法，对每一位建图跑一遍就行了。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 505

using namespace std;

int n,b[maxn][maxn],pre[maxn<<1],scc[maxn<<1],dfn[maxn<<1],low[maxn<<1];
int cnt,sta[maxn<<1],h,p,num;
bool vis[maxn<<1];
struct edge
{
    int u,v,next;
};
edge e[maxn*maxn*4];

void addedge(int u,int v)
{
    e[cnt].u=u; e[cnt].v=v;
    e[cnt].next=pre[u]; pre[u]=cnt++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=p++;
    vis[u]=1; sta[h++]=u;

    for (int i=pre[u];i!=-1;i=e[i].next)
    {
        int v=e[i].v;
        if (!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if (vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u])
    {
        int v;
        do
        {
            v=sta[--h];
            vis[v]=0;
            scc[v]=num;
        }
        while (v!=u) ;
        num++;
    }
}

int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        for (int i=0;i<n;i++)
            for (int j=0;j<n;j++) scanf("%d",&b[i][j]);
        bool f=0;
        for (int k=0;k<32;k++)
        {
            memset(pre,-1,sizeof(pre)); cnt=0;
            memset(dfn,0,sizeof(dfn)); num=0;
            memset(low,0,sizeof(low)); p=1;
            memset(scc,0,sizeof(scc)); h=0;

            for (int i=0;i<n;i++)
                for (int j=0;j<i;j++)
            {
                if ((i&1) && (j&1) ) // |
                {
                    if ((1<<k)&b[i][j]) addedge(i*2+1,j*2),addedge(j*2+1,i*2);
                    else addedge(i*2,i*2+1),addedge(j*2,j*2+1);
                }
                else if (!(i&1) && !(j&1) ) // &
                {
                    if ((1<<k)&b[i][j]) addedge(i*2+1,i*2),addedge(j*2+1,j*2);
                    else addedge(i*2,j*2+1),addedge(j*2,i*2+1);
                }
                else if ((1<<k)&b[i][j])
                {
                    addedge(i*2,j*2+1); addedge(j*2+1,i*2);
                    addedge(j*2,i*2+1); addedge(i*2+1,j*2);
                }
                else
                {
                    addedge(i*2,j*2); addedge(j*2,i*2);
                    addedge(i*2+1,j*2+1); addedge(j*2+1,i*2+1);
                }
            }
            for (int i=0;i<2*n;i++) if (!dfn[i]) tarjan(i);
            for (int i=0;i<2*n;i+=2) if (scc[i]==scc[i+1])
            {
                f=1; break;
            }
            if (f) break;
        }
        if (f) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}