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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Zoj1015】【弦图】【Fishing Net】  

2014-05-08 21:48:47|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:判断某个图是否是弦图。

    权当复习一下最大势算法求完美消除序列以及判断某个序列是否是完美消除序列。
    首先咱们求出这个图的一个伪完美消除序列,然后判断这个序列是否是完美消除序列即可。两个在CDQ的论文里面都提到了。前一个便是最大势算法,后一个便是一个结论。这里试了实现Jcvb君以前提供的一个O(n+m)的MCS【最大势】桶算法求完美消除序列【以前只会O((n+m)logn)的...】。【传送门
    然后到这里就基本上可以A了。
    0.0感觉写萎了额...因为跑了600ms了= =

=======================

program zoj1015;
const maxn=1010;
type edge=record
     v,pre:longint;
     end;

var last,las:array[0..maxn]of longint;
    e:array[0..maxn*maxn shl 1]of edge;
    mcs:array[0..maxn*maxn shl 1]of edge;
    eng,p,flag:array[0..maxn]of longint;
    can:array[0..maxn]of boolean;
    n,m,best,tot,tott:longint;

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 addedge2(u,v:longint);
begin
  inc(tott);mcs[tott].v:=v;mcs[tott].pre:=las[u];las[u]:=tott;
end;

procedure init;
var i,tmp,v,u:longint;
begin
  tot:=0;tott:=0;
  fillchar(last,sizeof(last),0);
  fillchar(las,sizeof(las),0);
  for i:=1 to m do
   begin
     read(u,v);
     addedge(u,v);
   end;
  fillchar(eng,sizeof(eng),0);
  fillchar(can,sizeof(can),true);
  fillchar(p,sizeof(p),0);
  fillchar(flag,sizeof(flag),0);
  best:=0;
  for i:=1 to n do addedge2(0,i);
  for i:=n downto 1 do
   begin
     while true do
     begin
      tmp:=las[best];
      while (tmp<>0)and(not can[mcs[tmp].v]) do
        begin
          tmp:=mcs[tmp].pre;
          las[best]:=tmp;
        end;
      if tmp<>0 then break;
      dec(best);
     end;
     v:=mcs[tmp].v;
     can[v]:=false;
     p[i]:=v;
     tmp:=last[v];
     while tmp<>0 do
      begin
        if can[e[tmp].v] then
          begin
            inc(eng[e[tmp].v]);
            addedge2(eng[e[tmp].v],e[tmp].v);
            if best<eng[e[tmp].v] then best:=eng[e[tmp].v];
          end;
        tmp:=e[tmp].pre;
      end;
   end;
  fillchar(flag,sizeof(flag),0);
  fillchar(can,sizeof(can),false);
  for i:=n downto 1 do
   begin
     v:=p[i];
     tmp:=last[v];
     while (tmp<>0)and(not can[e[tmp].v])do
      tmp:=e[tmp].pre;
     if tmp=0 then
      begin
        can[v]:=true;
        continue;
      end;
     u:=e[tmp].v;
     tmp:=last[u];
     flag[u]:=u;
     while tmp<>0 do
      begin
        if can[e[tmp].v] then
            flag[e[tmp].v]:=u;
        tmp:=e[tmp].pre;
      end;
     tmp:=last[v];
     while tmp<>0 do
      begin
        if (can[e[tmp].v])and(flag[e[tmp].v]<>u) then
          begin
            writeln('Imperfect');
            exit;
          end;
        tmp:=e[tmp].pre;
      end;
     can[v]:=true;
   end;
  writeln('Perfect');
end;

begin
  read(n,m);
  while (n<>0)and(m<>0)do
   begin
     init;
     writeln; 
     read(n,m);
   end;
end.

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

历史上的今天

评论

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

页脚

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