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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj1997】【Hnoi2010】【Planar】  

2014-04-23 20:51:23|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:平面图判定【吓傻了...】,保证是存在哈密顿回路的图。
   
   平面图!! 
   哈密顿回路!!
   蒟蒻最怕的两个词!!QAQ

   不过咱们要冷静一些额..0.0,首先咱们已经得到了一条哈密顿回路,咱们假设这个图是可以平面嵌入的【是这样说的哈?0.0?】,那么咱们显然可以在平面图上找到这个哈密顿回路,它对应平面上的一个环。

    0.0不过这有什么用呢?咱们考虑下,如何把所有的边弄进去...实际上,咱们发现,咱们可以把所有的边分成两类,一种是在这个环所围成的区域内部,一种是在这个环所围成的区域外。这两种边是互不干扰的,所以咱们只需考虑其中一种即可。咱们考虑到什么时候是不可能进行嵌入的?

    为了方便咱们把环拆成链,这样子每一条边实际上可以表示成一个区间。然后咱们可以发现,交叉了的区间必然不可能同时嵌入...也就是说这两个区间必须在不同的地方,即一个必须在环内部,一个必须在环外部...由于环内外并没有什么特殊性,所以咱们随便让一个在内部,一个在外部即可。那么------

    咱们枚举每两条边,如果他们的区间重合了,就把它们连一条边,那么咱们发现...咱们的任务实际上就是判断这个图能否划分成两边,然后每一边的任意两点没有边相连,实际上就是判断二分图!!!

    但是感觉M太大了怎么破0.0...枚举两条边的时候O(M^2)....
    想了半天不知道怎么优化额...因为要连边的话感觉最坏情况的确是O(M^2)条边... 然后跑去看ydc君的题解:【传送门
    丽洁姐也有一个神奇的解法...线段树...【传送门】【话说咱看不懂额】....
    发现了一件喜闻乐见的事情了0v0......

    不过为什么平面图的  边数<=点数x3-6      0.0?

    咱们来证明一下吧~ 0.0
    【以下证明不知道正确性0.0如果有错误求轻喷额..不过很多的确都是脑洞...】
    【下面的还需要修改修改,应该就可以了?0.0】
    【另外看到黑书直接一句由欧拉定理得到这个结论...咱不知道那个怎么做的额...】

     首先显然这个环可以转化成链,因为假设跨越了链的部分和其他部分有矛盾,实际上也可以对应到链的那一部分和其他部分有矛盾,所以看成链是蛮好的。

     首先咱们可以构造出一个解...那就是首先连哈密顿环,然后咱们在点1,向第3,4,5...n-1个点在环的内部连一条边,然后在点2,向第4,5,6...n个点在环的外部连一条边,很容易知道这里的边并没有重复的,然后也是可行的,它的边的个数也的确是3*v-6,现在咱们需要证明的就是不存在更优的策略即可。
     实际上咱们只需要证明内部或者外部中的一个最多能连的边<=n-3即可【这里的3*v-6的方案内部外部都达到了最大的边数n-3】,然后这个结论一开始以为是错的,然后就发现了貌似是可能2333333...

     咱们的每一个方案实际上可以看做,从第1个点开始往后面某个点连边,然后第二个点接着来,以此类推。咱们可以发现,若第i个点在第i-1个点连的某两条边间的话,那么它也只能连这两条边形成的区间【l,r】之间的与它不相邻的点,这个貌似可以产生一个类似的子问题,所以咱们现在来归纳一下,【l,r】能产生连的边<r-l-1。首先对于[l,l+1]这是显然的,由于哈密顿回路已经有边[l,l+1],所以咱们不能连,即0条边能连,现在咱们考虑从l向某一个点q连边,那么咱们可以把这个区间划分成 [l,q]和[q+1,r],但是咱们又知道 l不能和l+1连边,所以应该可以加强区间 [l+1,q]和[q+1,r],它们能连的边应该是 [l+1,q]+[q+1,r]+1,由于归纳,[l+1,q]和[q+1,r]是满足的,即 [l+1,q]<q-l-1,而[q+1,r]<r-q-1,则咱们有 [l+1,q]+[q+1,r]+1<r-l-1 这个证明成功的话,那么咱们发现...这个归纳得到结论就是 【1,n】能产生的边<n-1-1=n-2,也就是说最多就是n-3条!!
 
    咱们的证明貌似成功了?0.0所以最多能产生的边便是2*n-6[环内环外各n-3条]+n[哈密顿的]=3*n-6.
  
=========================

program bzoj1997;
{$m 1000000}
const maxm=10010;
      maxn=210;

type edge=record
     v,pre:longint;
     end;

var a,b,w:array[0..maxm*2]of longint;
    cir,c:array[0..maxm*2]of longint;
    n,m,tot,t:longint;
    e:array[0..maxm*5]of edge;
    last:array[0..maxm]of longint;
    flag:boolean;

procedure addedge(u,v:longint);
begin
  inc(tot);e[tot].v:=v;e[tot].pre:=last[u];last[u]:=tot;
  inc(tot);e[tot].v:=u;e[tot].pre:=last[v];last[v]:=tot;
end;

procedure dfs(p:longint);
var tmp:longint;
begin
  tmp:=last[p];
  while tmp<>0 do
   begin
     if w[e[tmp].v]=-1 then
      begin
        w[e[tmp].v]:=w[p] xor 1;
        dfs(e[tmp].v);
        if not flag then exit;
      end
     else
      if w[e[tmp].v] xor w[p]=0 then
        begin
          flag:=false;
          exit;
        end;
     tmp:=e[tmp].pre;
   end;
end;

procedure init;
var i,j:longint;
begin
  read(n,m);
  for i:=1 to m do
   read(a[i],b[i]);
  for i:=1 to n do
   begin
    read(cir[i]);
    c[cir[i]]:=i;
   end;
  if n*3-6<m then
   begin
     writeln('NO');
     exit;
   end;
  for i:=1 to m do
   if c[a[i]]>c[b[i]] then
    begin
      j:=a[i];a[i]:=b[i];b[i]:=j;
    end;
  fillchar(last,sizeof(last),0);
  tot:=0;
  for i:=1 to m do
   for j:=1 to m do
    if i<>j then
     if c[a[i]]+1<>c[b[i]] then
     if c[a[j]]+1<>c[b[j]] then
      if (c[a[i]]<c[a[j]])and(c[b[i]]>c[a[j]])and(c[b[j]]>c[b[i]]) then
      addedge(i,j);
  fillchar(w,sizeof(w),255);
  flag:=true;
  for i:=1 to m do
   if w[i]=-1 then
    begin
      w[i]:=0;
      dfs(i);
      if not flag then break;
    end;
  if flag then writeln('YES')
          else writeln('NO');
end;

begin
  read(t);
  for t:=1 to t do
    init;
end.

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

历史上的今天

评论

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

页脚

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