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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1064】【Noi2008】【假面舞会】  

2014-03-21 16:01:39|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     看到这题一堆面具...不自觉的想起 金田一少年事件簿 的游戏馆杀人囧.... 

     题目大意:   
     一些点,给出某些点的部分邻接关系,然后与某一个点相连的点必须放在同一组内,问在满足左述条件的情况下,最少能分多少组,最多能分多少组?

     = =怎么一看就不会做的感觉233....

     实际上每一种合法的方案最后都会构成一个环,环的每一段都是一堆点集。
     咱们可以用标号先DFS出一些点可能的编号,先随便找个点标号为1,然后是它的后继的标号为2,它本人是后继的走前继标号为0,然后这样就可以DFS出一堆又一堆的有层次的点集。
      以下{}内不是题解
      {
      然后貌似发现一个很好的事情,假设所有的都没有环的话,那是极好的0 0,那么最大的答案显然就是这些点集的标号的最大值减去最小值+1的和,也就是说把这些点堆连起来。最小值就是这些点堆中的最大值,显然其余的点堆都可以插进去。然后假设有环而且有两种长度不同的环,显然无解(这两种环不能同时满足)。然后只有一种长度的环且其他的点堆的大小不超过这个长度,那么就只有一个解,否则也是无解(其他点堆插不进这个环)
      然后这道题貌似就是 DFS+乱搞就可以过了???0 0 
      }
      然后以为自己想到了正解,喜闻乐见地去看题解检查= =  还可以戳Byvoid君的 感觉讲的最详细的就是lyd君
        非常,的漏掉了很多情况233。
    
      咱以后还是晚些再看题解.....这样太不科学了....
      加上咱的DFS,按上面的那种分类讨论即可。
      这里有个技巧可以不判断前驱后继啥的,就是把有向边做成无向边,其中一条边权为1,另一条为-1。然后找环,如果不是环则记录这个树的长度。
=======================================

program bzoj1064;
const maxm=1000010;
      maxn=100010;
type edge=record
     v,w,pre:longint;
     end;

var e:array[0..maxm*2]of edge;
    last,d:array[0..maxn]of longint;
    v:array[0..maxn]of boolean;
    n,m,ans,max,tot:longint;
    cir:boolean;

function gcd(a,b:longint):longint;
begin
  if b=0 then exit(a)
  else exit(gcd(b,a mod b));
end;

procedure dfs(p:longint;var min,max:longint);
var tmp:longint;
begin
  v[p]:=true;
  tmp:=last[p];
  while tmp<>0 do
   begin
     if v[e[tmp].v] and (d[e[tmp].v]<>d[p]+e[tmp].w) then
      begin
        if cir then ans:=gcd(ans,abs(d[e[tmp].v]-d[p]-e[tmp].w))
               else ans:=abs(d[e[tmp].v]-d[p]-e[tmp].w);
        cir:=true; 
      end;
     if not v[e[tmp].v] then
      begin
        d[e[tmp].v]:=d[p]+e[tmp].w;
        if min>d[e[tmp].v] then min:=d[e[tmp].v];
        if max<d[e[tmp].v] then max:=d[e[tmp].v];
        dfs(e[tmp].v,min,max);
      end;
     tmp:=e[tmp].pre;
   end;
end;

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

procedure init;
var i,u,vv:longint;
begin
  read(n,m);
  fillchar(last,sizeof(last),0);
  tot:=0;
  for i:=1 to m do
   begin
     read(u,vv);
     addedge(u,vv);
   end;
  max:=0;cir:=false;ans:=-1;
  fillchar(d,sizeof(d),0);
  fillchar(v,sizeof(v),false);
  for i:=1 to n do
    if not v[i] then
     begin
      u:=0;vv:=0;
      dfs(i,vv,u);
      max:=max+u-vv+1;
     end;
  if not cir then
   begin
     if max<3 then write(-1,' ',-1)
     else write(max,' ',3);
   end
  else
   begin
     if ans<3 then write(-1,' ',-1)
     else
      begin
        write(ans,' ');
        for i:=3 to ans do
         if ans mod i=0 then break;
        write(i);
      end;
   end;
end;

begin
  init;
 end.

    
  评论这张
 
阅读(103)| 评论(13)
推荐 转载

历史上的今天

评论

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

页脚

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