题解 P3209 【[HNOI2010]平面图判定】

· · 题解

前言

这题其实用不上 2-SAT ， Dinic ， Topo+Tarjan , disjoint-set 这么高大上的名词来解释的（其实是我太蒻了qwq）要我说就是爆搜，只不过保证了时间复杂度和正确性

大家的思路其实本质都差不多，代码实现起来除了 Tarjan 那个之外实质都一样，但却硬要提到二分图上，吓得我这种菜鸡当场劝退了

以防后面的人也会跟我一样被吓着，我决定用比较易懂的方式解释一下 qwq

一些必须想明白的事

题目中给了图中的哈密顿路径，这意味着图中的所有结点都连成了一个环。但是环上只有 n 条边，剩下的边去哪了呢？自然是把环上不相邻的两点给连接起来了

暂且先把除了哈密顿路径的所有边成为“弦”

想想环把平面分成了两个部分，那么如果两条弦相交了，使此图不为平面图，那么这两条弦肯定在环的同侧（内或外）

只在同侧就行了吗？

设结点 i 在环上的顺序为 HamiN_i ，那么两条弦相交还得满足一条弦的结点 a 的 HamiN 在另一条弦两个结点的 HamiN 的开区间内，另一结点 b 不在其闭区间内

设有两条边 x,y ，用表达式就写成：

HamiN_{x.a}<HamiN_{y.a}<HamiN_{x.b}

并且

HamiN_{y.b}<HamiN_{x.a} || HamiN_{x.b}<HamiN_{y.b}

把 y 的 a,b 再对调一下进行比较：

HamiN_{x.a}<HamiN_{y.b}<HamiN_{x.b}

并且

HamiN_{y.a}<HamiN_{x.a} || HamiN_{x.b}<HamiN_{y.a}

两者满足其一，同侧两弦就相交

代码写上来就是

bool Intersect(DE x,DE y)
{
    return
    (
        (
            (HamiN[y.a]<HamiN[x.a] && HamiN[x.a]<HamiN[y.b])
            && 
            (HamiN[x.b]<HamiN[y.a] || HamiN[y.b]<HamiN[x.b])
        )
        ||
        (
            (HamiN[y.a]<HamiN[x.b] && HamiN[x.b]<HamiN[y.b])
            && 
            (HamiN[x.a]<HamiN[y.a] || HamiN[y.b]<HamiN[x.a])
        )
    );
}

注意提前预处理出 HamiN 并使得每条弦 HamiN_a \leq HamiN_b 

scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++) E[i].Scan();
for(int i=1,V;i<=n;i++)
{
    scanf("%d",&V);
    HamiN[V]=i;
}
for(int i=1;i<=m;i++)
    if(HamiN[E[i].a]>HamiN[E[i].b]) swap(E[i].a,E[i].b);

算法思路

如果图上所有弦不管向内向外如何摆放都会有相交，那么这个图就不是平面图

如果存在有一种摆放方式使所有弦都不相交，那么就是平面图

我们只要尽量让图成为平面图就行了

对于每一条弦，找出所有有可能与之相交的弦（就是如果放在同侧它俩就会相交，它们组成的集合称为 oppo ），那么这条弦放在了一侧，其 oppo 内所有弦必须放在异侧

我们每放一条弦，就将其的 oppo 内所有边放进异侧，如果这期间有边相交了，那就没办法了，肯定不是平面图

对于一开始放置的弦，我们放在哪侧都行

整个放置的过程用 DFS 实现，样子很像你们匹配二分图时的样子

效率 O(Tm^2) ，由于 m\leq3n-6 ，根本不慌

代码实现

#include<bits/stdc++.h>
using namespace std;

const int MAXN=200;
const int MAXM=1e4;

bool inseg(int bef,int ob,int aft)
{return bef<ob && ob<aft;}

struct DE
{
    int a,b;
    void Scan() {scanf("%d %d",&a,&b);}
    void Print() {printf("%d %d\n",a,b);}
}E[MAXM+5];

int T,n,m;bool ans;
int HamiN[MAXN+5];
DE Assort[3][MAXN+5];int num[3];
//记录两侧有哪些弦放置

bool Intersect(DE x,DE y)
{
    return
    (
        (
            (HamiN[y.a]<HamiN[x.a] && HamiN[x.a]<HamiN[y.b])
            && 
            (HamiN[x.b]<HamiN[y.a] || HamiN[y.b]<HamiN[x.b])
        )
        ||
        (
            (HamiN[y.a]<HamiN[x.b] && HamiN[x.b]<HamiN[y.b])
            && 
            (HamiN[x.a]<HamiN[y.a] || HamiN[y.b]<HamiN[x.a])
        )
    );
}

bool cmp(DE x,DE y)
{
    if(HamiN[x.a]!=HamiN[y.a]) return HamiN[x.a]<HamiN[y.a];
    return HamiN[x.b]<HamiN[y.b];
}

bool CanPutIn(DE ob,bool type)//判断弦 ob 是否能放在 type 侧
{
    for(int i=1;i<=num[type];i++)
        if(Intersect(ob,Assort[type][i])) return 0;
    return 1;
}

struct msg
{
    bool type;
    int edge;
};

vector<int> oppo[MAXM+5];
bool visit[MAXM+5];

bool DFS(int edge,bool type)
{
    visit[edge]=1;
    Assort[type][++num[type]]=E[edge];
    bool cnt=1;
    for(int i=0,rear;i<oppo[edge].size() && cnt;i++)
    {
        rear=oppo[edge][i];
        if(visit[rear]) continue;
        if(CanPutIn(E[rear],!type)) cnt&=DFS(rear,!type);
        else cnt=0;
    }
    return cnt;
}

int main()
{
    for(scanf("%d",&T);T--;)
    {
        scanf("%d %d",&n,&m);
        for(int i=1;i<=m;i++) E[i].Scan();
        for(int i=1,V;i<=n;i++)
        {
            scanf("%d",&V);
            HamiN[V]=i;
        }
        for(int i=1;i<=m;i++)
            if(HamiN[E[i].a]>HamiN[E[i].b]) swap(E[i].a,E[i].b);
        if(m>3*n-6) {printf("NO\n");continue;}
        num[0]=num[1]=0;
        ans=1;
        for(int i=1;i<=m;i++)
        {
            oppo[i].clear();
            visit[i]=0;
        }
        for(int i=1;i<=m;i++)
            for(int j=1;j<=m;j++)
            {
                if(i==j) continue;
                if(Intersect(E[i],E[j])) oppo[i].push_back(j);
            }
        for(int i=1;i<=m && ans;i++)
            if(!visit[i]) ans&=DFS(i,0);
        //如果 !visit[i]，说明弦 i 跟之前放置的弦绝对不会相交，因此可以随意放置弦 i
        if(ans) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

后语

不看也行，没啥用

一开始看到这题第一反应是库拉托夫斯基定理 qwq 满图找 K_5 （五个结点的无向完全图）和 K_{3,3} （两部有三个结点的二分图，不同部的结点都互相有连边）

然后效率是…… O(Tn^6) qwq 直到我看到题目中给了哈密顿回路……

然后想了个假算法：依次放置所有边，能放进内侧就放内侧，不行就外侧，再不行直接输出 NO

其实写到一半一经发现算法假了，然而不甘心，按照弦两侧结点的 HamiN 排序了一下

居然拿了 80 分 qwq 考场上如果想不出来这方法肯定值了