[HNOI2010] PLANAR

Problem

给定一个图,告诉你图的一条哈密顿回路,判定该图是否为一个平面图。

Solution

平面图的定义:一个图,放置在平面上,任意边皆不相交。这种图叫做平面图。
欧拉定理:设多个多边形的节点数,边数和分割的平面数分别为$n,m,c$,相交的连同块的个数为f,则$n-m+c=f+1$。 对于一个极大平面图,由于一个面会使用一定三条边(即使是4条边,由于极大,也被分割成了3条边的面),而每条边一定被共用两次。所以有:$2c=3m$。 将两个算式合并,得到极大平面图$3n-6=m$。则若$m>3n-6$,该图不可能为平面图。

给出了哈密顿回路相当于给出了一个圈。
一条边可以从圈内一条直线连过去,也可以弯到圈外来连。
由于给出了哈密顿回路,只需判断两边若连圈内是否相交。如果相交,则这两条边要么一个圈内一个圈外。

可以转化成2-SAT求解。
实际上也等价于二分图染色求解。

Code

// Code by ajcxsu
// Problem: planar

#include<bits/stdc++.h>
#define CLR(x) memset(x,0,sizeof(x))
#define DEBUG cout<<"Passing Line "<<__LINE__<<" in "<<__FUNCTION__<<"..."<<endl
using namespace std;

const int N=10000,M=1e5;

struct Edge {
    int u,v;
} e[N];

int ran[N];

int h[N],to[M],nexp[M],p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }

bool flag;
int col[N];
void paint(int x,int nc) {
    for(int u=h[x];u && !flag;u=nexp[u])
        if(!col[to[u]]) col[to[u]]=nc^1, paint(to[u], nc^1);
        else if(col[to[u]]==nc) flag=1;
}

void init() { CLR(h), p=1; flag=0; CLR(col); }
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    int n,m;
    while(T--) {
        init();
        cin>>n>>m;
        for(int i=0;i<m;i++) cin>>e[i].u>>e[i].v;
        int na;
        for(int i=1;i<=n;i++) cin>>na, ran[na]=i;
        if(m>3*n-6) { cout<<"NO"<<endl; continue; }
        for(int i=0;i<m;i++) {
            e[i].u=ran[e[i].u], e[i].v=ran[e[i].v];
            if(e[i].u>e[i].v) swap(e[i].u, e[i].v);
        }
        Edge a,b;
        for(int i=0;i<m;i++)
                for(int j=i+1;j<m;j++) {
                    a=e[i], b=e[j];
                    if(a.u>b.u) swap(a,b);
                    if(b.u>a.u && b.u <a.v && a.v>b.u && a.v<b.v) ins(i,j), ins(j,i);
                }
        for(int i=0;i<m && !flag;i++)
            if(!col[i]) paint(i,2);
        if(flag) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

本文链接:https://acxblog.site/archives/sol_luogu_p3209.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。