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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1006】【HNOI2008】【神奇的国度】  

2014-02-19 22:03:56|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
        弦图是啥详见 CDQ神犇的PPT,百度弦图很容易找到。所以具体的东西就不记下来了。里面有几个引理没有证明表示还是想耿耿于怀很久的....
        我们先O((n+m)logN)的最大势算法求出完美消除序列(至于为什么不是CDQ的O(n+m),表示咱根本没看懂CDQ神犇的那个桶是什么....,所以用堆的话就是这样了...)。(PS:另外据前人的试验,这题暴力就可以过了...)O(n^2+m)
        然后从完美消除序列倒着染色就可以了(为什么可以呢?这实际上就是把原图处理出成一个层次图了,所以类似贪心的方法...),每到一个节点,扫描它的邻接点中染过的颜色,选一个没染的颜色染即可。
*******补充************
        另外附神奇的O(n+m)的方法:
        如果上面的地址不行可以复制到地址栏去
        orz..........................
        【BZOJ1006】【HNOI2008】【神奇的国度】 - z55250825 - z55250825
  
===========================================

program bzoj1006;
const maxn=10010;
      maxm=1000010;
type edge=record
     v,pre:longint;
     end;
var n,m,tot:longint;
    e:array[0..maxm shl 1]of edge;
    last:array[0..maxn]of longint;
    l,num,col,h:array[0..maxn]of longint;
    v:array[0..maxn]of 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 init;
var i,j,k,u,w,ans:longint;
begin
  read(n,m);
  tot:=0;
  fillchar(last,sizeof(last),0);
  for i:=1 to m do
   begin
     read(u,w);
     addedge(u,w);
   end;
  fillchar(l,sizeof(l),0);
  fillchar(v,sizeof(v),false);
  l[0]:=-1;
  for i:=n downto 1 do
  begin
   j:=0;
   for k:=1 to n do
    if (l[k]>l[j])and(not v[k]) then
     j:=k;
   num[i]:=j;
   v[j]:=true;
   k:=last[j];
   while k<>0 do
    begin
      inc(l[e[k].v]);
      k:=e[k].pre;
    end;
  end;
  fillchar(col,sizeof(col),0);
  fillchar(h,sizeof(h),0);
  ans:=1;
  for i:=n downto 1 do
   begin
     j:=num[i];
     k:=last[j];
     while k<>0 do
      begin
        h[col[e[k].v]]:=i;
        k:=e[k].pre;
      end;
     for k:=1 to ans+1 do
      if h[k]<>i then
       begin
        col[j]:=k;
        break;
       end;
     if col[j]=ans+1 then inc(ans);
   end;
  write(ans);
end;

begin
  init;
end.






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

历史上的今天

评论

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

页脚

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