POJ - 3207 Ikki's Story IV - Panda's Trick (2-SAT)

(点击此处查看原题)

题意

有n个点按顺序排列在一个圆上,编号依次为0~n-1,在n点之间有m条边,这些边可以在圆内连接两点,也可以在圆外连接两点(如下图所示),问是否存在一种连接法,使得m条边不相交。

POJ - 3207  Ikki's Story IV - Panda's Trick (2-SAT)

 

解题思路

我们发现对于每条边,只存在两种状态:圆内、圆外,而且某些边之间存在矛盾关系,显然,这是一个2-sat问题,我们记a表示圆内的边,¬a表示圆外的边

由于输入只给出了某两点之间存在的边,而没有给出边的矛盾关系,那么我们需要将所有边存储下来,随后处理出边之间的矛盾关系。

 POJ - 3207  Ikki's Story IV - Panda's Trick (2-SAT)

 

如上图所示右边的两条边,发现如果某两条在内部的边相交,那么对应的在外部边也相交,所以对于冲突的两边a,b,必满足 a → ¬b Λ b → ¬a,表示a,b不同时出现在圆内和圆外

而对于两条在内部的边不相交,其对应的在外部的边也不交,同时一条在内,一条在外的边也不相交,说明不存在矛盾关系,无需处理

总结:我们先记录下所有的边,用i表示位于内部的边,用i+n表示其对应的位于外部的边,随后用m^2的复杂度枚举每条边和其余边,判断是否存在矛盾关系,如果两条边在内部或者外部相交,那么必定满足a → ¬b Λ b → ¬a,所以我们在a和b+n,b和a+n之间分别建一条无向边,然后我们用tarjan在图中求出强连通分量SCC,最后枚举每条边x,判断x和¬x是否处于同一强连通分量,如果每条边的内部和外部的边都不在同一强连通分量中,那么就是正确的,反之错误

 代码区

POJ - 3207  Ikki's Story IV - Panda's Trick (2-SAT)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<fstream>
#include<vector>
#include<stack>
#include <map>
#include <iomanip>

#define bug cout << "**********" << endl
#define show(x, y) cout<<"["<<x<<","<<y<<"] "
#define LOCAL = 1;
using namespace std;
typedef long long ll;
const ll inf = 2e9 + 10;
const ll mod = 1e9 + 7;
const int Max = 1e4 + 10;
const int Max2 = 3e2 + 10;

int n, m;
vector<int> edge[Max];
pair<int, int> way[Max];            //存边
int dfn[Max],low[Max],time_clock;
int id[Max],sccCnt;
int line[Max],now;

void init()
{
    for(int i = 0;i < Max; i ++)
        edge[i].clear();
    memset(dfn,0,sizeof(dfn));
    time_clock = 0;
    sccCnt = 0;
    memset(id,0,sizeof(id));
    now = 0;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++time_clock;
    line[++now] = u;
    for(vector<int>::iterator it = edge[u].begin(); it != edge[u].end();++it)
    {
        int v = *it;
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(!id[v])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(dfn[u] == low[u])
    {
        sccCnt++;
        while(line[now] != u)
            id[line[now--]] = sccCnt;
        id[line[now--]] = sccCnt;
    }
}

int main()
{
#ifdef LOCAL
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    while (scanf("%d%d", &n, &m) != EOF)
    {
        init();
        for (int i = 1, u, v; i <= m; i++)
        {
            scanf("%d%d", &u, &v);
            if (u > v)
                swap(u, v);                //方便起见,处理一下
            way[i].first = u;
            way[i].second = v;
        }
        for (int i = 1; i <= m; i++)
        {
            for (int j = i + 1; j <= m; j++)
            {
                int num =0;
                if(way[i].first < way[j].first && way[j].first < way[i].second)
                    num++;
                if(way[i].first < way[j].second && way[j].second < way[i].second)
                    num++;
                if(num == 1)                    //两边冲突,只有一边内一边外才合法
                {
                    edge[i].push_back(j+m);
                    edge[j+m].push_back(i);        //i在内,j在外
                    edge[j].push_back(i+m);
                    edge[i+m].push_back(j);        //i在外,j在内
                }
            }
        }
        for(int i = 1;i <= (m<<1);i ++)
        {
            if(!dfn[i])
                tarjan(i);
        }
        bool ok = true;
        for(int i = 1;i <= m ;i ++)
        {
            if(id[i] == id[i+m])                //处于同一强连通分量中,说明无解
            {
                ok = false;
                break;
            }
        }
        if(ok)
            printf("panda is telling the truth...\n");
        else
            printf("the evil panda is lying again\n");
    }
    return 0;
}
View Code

 

上一篇:Story of Jerry Wang's Wechat subscription account


下一篇:牛客java专项练习-day16