[POJ3207]Ikki’s Story IV – Panda’s Trick【2-SAT】

Ikki’s Story IV – Panda’s Trick

【题目描述】

传送门

【题目大意】

平面上有一个圆,圆的边上按顺时针放着0..n-1共n个点。现在要连m条边,比如a,b,那么a到b可以从圆的内部连接,也可以从圆的外部连接。给你的信息中,每个点最多只能连一条边。问是否可以连接这m条边,使这些边都不相交。

【题解】

我们读题可知,每条边只有两种情况,那么就可以套2-SAT了,对于一对相交的边(i,j),建双向边i * 2<->j * 2+1,j * 2<->i * 2+1,然后套一下板子就可以了。

【代码如下】

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int MAXN=505;
int n,m,Top,Stk[MAXN<<1];
bool vis[MAXN<<1];
struct Edge{
    int tot,lnk[MAXN<<1],son[MAXN*MAXN<<3],nxt[MAXN*MAXN<<3];
    void Add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
struct xcw{int x,y;}a[MAXN];
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
    return f?ret:-ret;
}
bool DFS(int x){
    if(vis[x^1]) return 0;
    if(vis[x]) return 1;
    Stk[++Top]=x;vis[x]=1;
    for(int j=E.lnk[x];j;j=E.nxt[j]) if(!DFS(E.son[j])) return 0;
    return 1;
}
bool Solve(){
    for(int i=1;i<=m;i++)
    if(!vis[(i-1)<<1]&&!vis[(i-1)<<1|1]){
        Top=0;
        if(!DFS((i-1)<<1)){
            while(Top) vis[Stk[Top--]]=0;
            if(!DFS((i-1)<<1|1)) return 0;
        }
    }
    return 1;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    n=read();m=read();
    for(int i=1;i<=m;i++){a[i]=(xcw){read(),read()};if(a[i].x>a[i].y) swap(a[i].x,a[i].y);}
    for(int i=1;i<=m;i++)
    for(int j=i+1;j<=m;j++)
    if(a[i].x<a[j].x&&a[i].y>a[j].x&&a[i].y<a[j].y||a[j].x<a[i].x&&a[j].y>a[i].x&&a[j].y<a[i].y)
    E.Add((i-1)<<1,(j-1)<<1|1),E.Add((j-1)<<1,(i-1)<<1|1),E.Add((j-1)<<1|1,(i-1)<<1),E.Add((i-1)<<1|1,(j-1)<<1);
    if(Solve()) printf("panda is telling the truth...\n");
    else printf("the evil panda is lying again\n");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部