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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1191&BZOJ1192】【Hnoi2006】【超级英雄&&鬼谷子的钱袋】  

2014-04-15 10:55:58|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   后者不想说啥了....就是 logn 向上取整。0.0代码嘛...应该都写得出来的感觉吧...
   前者是裸的二分图匹配,主要是复习匈牙利算法。复杂度O(nm)
   然后发现...咱又傻叉了,看错题目了233...选手必须答对这一题才能够进入下一题额= =WA一次。
==============================

program bzoj1191;
const maxn=4001;
type edge=record
     v,pre:longint;
     end;
 
var e:array[0..2001]of edge;
    v:array[0..2001]of boolean;
    h,last:array[0..2001]of longint;
    n,m,tot,ans:longint;
 
procedure addedge(u,v:longint);
begin
  inc(tot);e[tot].v:=v;e[tot].pre:=last[u];last[u]:=tot;
end;
 
function dfs(p:longint):boolean;
var tmp:longint;
begin
  tmp:=last[p];
  while tmp<>0 do
   begin
     if (not v[e[tmp].v]) then
      begin
        v[e[tmp].v]:=true;
        if (h[e[tmp].v]=0)or(dfs(h[e[tmp].v]))then
          begin
            h[e[tmp].v]:=p;
            exit(true);
          end;
      end;
     tmp:=e[tmp].pre;
   end;
  exit(false);
end;
 
procedure init;
var i,uu,vv:longint;
begin
  read(n,m);
  tot:=0;ans:=0;
  fillchar(last,sizeof(last),0);
  fillchar(h,sizeof(h),0);
  for i:=1 to m do
   begin
     read(uu,vv);
     addedge(i,uu);
     if uu<>vv then addedge(i,vv);
     fillchar(v,sizeof(v),false);
     if dfs(i) then inc(ans)
               else break;
   end;
  write(ans);
end;
 
begin
  init;
end.

  评论这张
 
阅读(23)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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