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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1051】【HAOI2006】【受欢迎的牛】  

2014-03-16 16:45:18|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   复习下Tarjan而已...缩点完之后是个DAG,如果有这样一个点满足题目要求的话,则一定只有它的出度为0,所以Tarjan之后统计出度为0的点,如果=1则输出那个出度为0的点,否则输出0。
    一开始,b了,直接统计入度然后找入度为num-1的(num为缩点数目),即使是DAG也有可能间接连接....
=======================================

program bzoj1051;
const maxn=10010;
type edge=record
     u,v,pre:longint;
     end;

var dfn,low,last,wh,tuan,du,st:array[0..maxn]of longint;
    n,m,num,tot:longint;
    link:array[0..maxn,0..maxn]of byte;
    e:array[0..maxn*5]of edge;

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

procedure tarjan(p:longint);
var tmp,t:longint;
begin
  tmp:=last[p];
  inc(tot);
  dfn[p]:=tot;
  low[p]:=tot;
  inc(st[0]);st[st[0]]:=p;
  while tmp<>0 do
   begin
     if dfn[e[tmp].v]=0 then tarjan(e[tmp].v);
     if low[p]>low[e[tmp].v] then low[p]:=low[e[tmp].v];
     tmp:=e[tmp].pre;
   end;
  if low[p]=dfn[p] then
   begin
     inc(num);
     repeat
       t:=st[st[0]];
       low[t]:=n+1;
       wh[t]:=num;
       inc(tuan[num]);
       dec(st[0]);
     until t=p;
   end;
end;

procedure init;
var i,u,v,w,ans:longint;
begin
  read(n,m);
  tot:=0;
  fillchar(last,sizeof(last),0);
  for i:=1 to m do
   begin
     read(u,v);
     addedge(u,v);
   end;
  fillchar(st,sizeof(st),0);
  fillchar(tuan,sizeof(tuan),0);
  fillchar(wh,sizeof(wh),0);
  fillchar(dfn,sizeof(dfn),0);
  fillchar(low,sizeof(low),0);
  fillchar(tuan,sizeof(tuan),0);
  w:=tot;tot:=0;num:=0;
  for i:=1 to n do
   if dfn[i]=0 then tarjan(i);
  fillchar(link,sizeof(link),0);
  fillchar(du,sizeof(du),0);
  for i:=1 to w do
   if wh[e[i].u]<>wh[e[i].v] then
    if link[wh[e[i].u]][wh[e[i].v]]=0 then
     begin
       link[wh[e[i].u]][wh[e[i].v]]:=1;
       inc(du[wh[e[i].u]]);
     end;
  ans:=0;tot:=0;
  for i:=1 to num do
    if du[i]=0 then
     begin
      ans:=i;
      inc(tot);
     end;
  if tot=1 then write(tuan[ans])
           else write(0);
end;

begin
  init;
end.


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

历史上的今天

评论

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

页脚

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