【bzoj1997】[Hnoi2010]Planar

2015.06.15 19:18 Mon | 24次阅读 | 旧日oi | 固定链接 | 源码

为了访问量,搞个完整的体面。
若能将无向图 G=(V,E)画在平面上使得任意两条无重合顶点的边不相交,则称 G 是平面图。
判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的
图,图中存在一个包含所有顶点的环,即存在哈密顿回路。
【输入格式】( input.txt)
从文件input.txt中读入数据, 输入文件第一行是一个正整数T,表示数据组数(每组数据
描述一个要判定的图)。 接下来从输入文件第二行开始有T组数据, 每组数据的第一行是用空格
隔开的两个正整数N和M,分别表示对应图的顶点数和边数。 紧接着的M行,每行是用空格隔开的
两个正整数u和v(1≤u,v≤N),表示对应图的一条边(u,v),输入的数据保证所有边仅出现一次。
每组数据的最后一行是用空格隔开的N个正整数, 从左到右表示对应图中的一个哈密顿回路: V1,
V2, „, VN,即对任意i≠j有Vi≠Vj且对任意1≤i≤N-1有(Vi,Vi+1)∈E及(V1,VN)∈E。 输入的数据
保证100%的数据满足T≤100,3≤N≤200,M≤10000
【输出格式】( output.txt)
输出文件 output.txt 包含 T 行,若输入文件的第 i 组数据所对应图是平面图, 则在第 i 行
输出 YES,否则在第 i 行输出 NO,注意均为大写字母。
【输入输出样例】
input.txt
2
6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
1 4 2 5 3 6
5 5
1 2
2 3
3 4
4 5
5 1
1 2 3 4 5
output.txt
NO
YES
题解
既然是个环,那么就可以转化为2-SAT问题了。首先根据平面图的性质,如果m>3n-6,一定无解,别问我为什么!!!
然后考虑什么样的边会相交,我在这里坑了好久,开始以为想的简单了,后来一顿特判,最后才发现开始想的是对的……
把点重标号后,如果一对点交叉分布,那么一定在内部相交,如果在内部相交,在外部也一定相交,这样的话就只能是一内一外了,于是连4条边把2sat建出来就OK了。
注意各种初始化问题……我恨多组数据!

我的程序

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define N 50005
struct edge
{
    int u,v,ban;
}e[N];
int T,n,m,tim,cnt;
int dfn[N],low[N],scc[N],rk[N];
stack<int> st;
vector<int> son[N];
void dfs(int u)
{
    dfn[u]=low[u]=++tim;st.push(u);
    for(int v,i=0;i<son[u].size();i++)
    {
        if(!dfn[v=son[u][i]])
        {
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!scc[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        cnt++;int x=-1;
        while(x!=u) scc[x=st.top()]=cnt,st.pop();
    }
}
bool check()
{
    for(int i=0;i<2*m;i++)
    if(scc[i]==scc[i^1]) return 1;
    return 0;
}
bool check(int a,int b,int c,int d)
{
    if(a<c&&c<b&&b<d) return 1;
    if(c<a&&a<d&&d<b) return 1;
    return 0;
}
void Init()
{
    for(int i=0;i<2*m;i++)
    {
        dfn[i]=low[i]=scc[i]=0;
        son[i].clear();
        e[i].ban=0;
    }
    cnt=tim=0;
    while(!st.empty()) st.pop();
}
int main()
{
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        Init();
        for(int i=0;i<m;i++)
            scanf("%d%d",&e[i].u,&e[i].v);
        for(int x,i=1;i<=n;i++)
        {
            scanf("%d",&x);
            rk[x]=i;
        }
        if(m>3*n-6){puts("NO");continue;}
        for(int i=0;i<m;i++)
        {
            e[i].u=rk[e[i].u];e[i].v=rk[e[i].v];
            if(e[i].u>e[i].v) swap(e[i].u,e[i].v);
            if(e[i].v==e[i].u+1||(e[i].v==n&&e[i].u==1)) e[i].ban=1;
        }
        for(int i=0;i<m-1;i++)
        for(int j=i+1;j<m;j++)
        if(!e[i].ban&&!e[j].ban&&check(e[i].u,e[i].v,e[j].u,e[j].v))
        {
            son[i*2+1].push_back(j*2);son[j*2+1].push_back(i*2);
            son[j*2].push_back(i*2+1);son[i*2].push_back(j*2+1);
        }
        for(int i=0;i<2*m;i++) if(!dfn[i]) dfs(i);
        if(check()) puts("NO");
        else puts("YES");
    }
}```