注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 1997(hnoi2010) 平面图判定  

2013-02-21 22:33:40|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

膜拜翱犇!!

直接将古楠的O(n)判定平面图的神代码给贴了上去啊!!

哈密尔顿回路神马的都不用读入了!!

 

我还是老老实实地用普通做法吧……

首先根据题意,我们画了一个哈密尔顿回路的圈圈。

那么剩下的边要不然在圈里面,要不然在圈外面。不过其实,在圈里面跟在圈外面是等价的。

我们只需要关注两条边能不能同时出现在一个区域即可,如果不能同在圈里就也不能同在圈外

所以就是二分图判定了

等等?m那么大根本跑不出来啊

出题人漆子超说:“我的标解是想用高级数据结构维护的。”

不过令超神始料未及的事情出现了——出数据的时候全都是NO

没错……平面图的边数小于等于三倍点数减六!!直接特判即可

很不爽的超神就把这个m的数据范围保留下来了……坑人用的

 

ORZ超神!!高级数据结构维护啊!!

ORZ翱犇!!平面嵌入都会写啊!!!

 

我是傻叉……

 

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXP 210
#define MAXN 600
#define MAXM 360000
using namespace std;
int pos[MAXP],edge[MAXN][2],n,m;
int tot,start[MAXN],to[MAXM],next[MAXM];
bool use[MAXN],color[MAXN];
void make(int a,int b){  tot++,to[tot]=b,next[tot]=start[a],start[a]=tot;  }
void Read(int &digit)
{
    digit=0;
    char c;
    for(c=getchar();c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
void read()
{
    Read(n),Read(m);
    for(int i=1,a,b;i<=m;i++)
    {
        Read(a),Read(b);
        if(m<=n*3-6)  edge[i][0]=a,edge[i][1]=b;
    }
    for(int i=1,a;i<=n;i++)
    {
        Read(a);
        pos[a]=i;
    }
}
void Make_Graph()
{
    for(int i=1;i<=m;i++)
        if(edge[i][1]-edge[i][0]!=1&&edge[i][1]-edge[i][0]!=n-1)
            for(int j=1;j<=m;j++)
                if(j!=i&&edge[j][1]-edge[j][0]!=1&&edge[j][1]-edge[j][0]!=n-1)
                    if((edge[i][1]-edge[j][0])*(edge[i][1]-edge[j][1])<0)
                        if((edge[j][0]-edge[i][0])*(edge[j][0]-edge[i][1])<0)
                            make(i,j),make(j,i);
}
bool paint(int p)
{
    use[p]=true;
    for(int i=start[p];i;i=next[i])
    {
        int q=to[i];
        if(use[q]==true&&color[q]==color[p])  return false;
        if(use[q]==false)
        {
            color[q]=color[p]^1;
            if(!paint(q))  return false;
        }
    }
    return true;
}
void work()
{
    if(m>n*3-6)
    {
        printf("NO\n");
        return ;
    }
    for(int i=1;i<=m;i++)
    {
        edge[i][0]=pos[edge[i][0]],edge[i][1]=pos[edge[i][1]];
        if(edge[i][0]>edge[i][1])  swap(edge[i][0],edge[i][1]);
    }
    tot=0;
    memset(start,0,sizeof(start));
    memset(use,false,sizeof(use));
    Make_Graph();
    for(int i=1;i<=m;i++)
        if(use[i]==false&&!paint(i))
        {
            printf("NO\n");
            return ;
        }
    printf("YES\n");
}
int main()
{
    int test;
    for(Read(test);test;test--)
    {
        read();
        work();
    }
    return 0;
}


  评论这张
 
阅读(395)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017