题解 P3209 【[HNOI2010]PLANAR】

· · 题解

其实不用2-sat的，直接并查集。

先用平面图定理 m<=3*n+6 把边数减小到O(n)级别。

然后设 集合 i+m 表示 不能与i共存的边 所在的集合。

枚举每一对不能共存的边，如果已经在同一个集合内，则无解。

否则交叉连边 fa[find(i)]=j+m , fa[find(j)]=i+m 。

如何判断两条边是否相交？先把所有边坐标转换为哈密顿回路中的顺序坐标，对于任意两条边i,j，如果有xi<xj<yi<yj，则相交。

注意如果两条边任意不在同一条边上的两端点相同则不可能相交。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2e3+1e1;

int x[maxn<<4],y[maxn<<4],vis[maxn<<4];
int id[maxn];
int fa[maxn<<5];
int T,n,m;

inline int findfa(int x)
{
    return fa[x] == x ? x : fa[x] = findfa(fa[x]);
}

inline void initfa()
{
    for(int i=1;i<=m<<1;i++)
        fa[i] = i;
}

inline bool cross(int x1,int x2,int y1,int y2)
{
    if( x1 == x2 || y1 == y2 || x1 == y2 || x2 == y1 )
        return 0;
    if( x1 < x2 && y1 < y2 && x2 < y1 )
        return 1;
    if( x2 < x1 && y2 < y1 && x1 < y2 )
        return 1;
    return 0;
}

inline bool check()
{
    initfa();
    for(int i=1;i<=m;i++)
    {
        if( vis[i] )
            continue;
        for(int j=1;j<=m;j++)
        {
            if( vis[j] )
                continue;
            if( !cross(x[i],x[j],y[i],y[j]) )
                continue;
            int fai = findfa(i) , faj = findfa(j);
            if( fai == faj )
                return 0;
            fa[fai] = findfa( j + m ),
            fa[faj] = findfa( i + m );
        }
    }
    return 1;
}

inline void init()
{
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    memset(vis,0,sizeof(vis));
    n = m = 0;
}

inline int getint()
{
    int ret = 0;
    char ch = getchar();
    while( ch < '0' || ch > '9' )
        ch = getchar();
    while( '0' <= ch && ch <= '9' )
        ret = ret * 10 + ( ch - '0' ),
        ch = getchar();
    return ret;
}
int main()
{
    T = getint();

    while( T-- )
    {
        init();
        n = getint() , m = getint();
        for(int i=1;i<=m;i++)
            x[i] = getint() , y[i] = getint();
        for(int i=1;i<=n;i++)
            id[getint()] = i;
        if( m > 3 * n + 6 )
        {
            puts("NO");
            continue;
        }
        for(int i=1,a,b;i<=m;i++)
        {
            a = id[x[i]] , b = id[y[i]];
            x[i] = min( a , b ),
            y[i] = max( a , b );
        }
        for(int i=1;i<=m;i++)
            if( y[i] == x[i] + 1 || ( y[i]==n && x[i]==0) )
                vis[i] = 1;
        if( check() )
            puts("YES");
        else puts("NO");
    }
    return 0;
}