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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Poj1149】【Pigs】  

2014-03-20 17:00:36|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    首先仰慕bzoj1062....现在还在努力理解= =
    然后这道题的题解可以戳这儿:网络流总结
   写的非常详细,蒟蒻就不详细写了....这道题的建图就按那个建立即可,至于为什么是对的也很容易想,实际上咱们就是把猪圈这个模型省略到了边中,而且这个模型可以满足以下条件:1.每个人得到的猪不超过他所想要的。2.每个猪圈确实只供应了这么多头猪。3.每次交易之后的交换确实可以体现(就是某些流不流这个人流向别的可以接受的人)所以就是对的。
    另外这道题的内存限制一开始没看清..没想到那么少= =,所以之后随便开小一点就A了。
=========================

program poj1149;
const maxm=4000;
      maxn=400;
type edge=record
     u,v,w,c,pre:longint;
     end;

var e:array[0..maxm]of edge;
    last,d,que:array[0..maxn]of longint;
    tot,n,m:longint;
    pig:array[0..maxn,0..maxn]of longint;
    v:array[0..maxn]of boolean;
    pignum:array[0..maxn]of longint;

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

function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;

function bfs(s,t:longint):boolean;
var l,r,u,tmp:longint;
begin
  fillchar(v,sizeof(v),false);
  fillchar(d,sizeof(d),0);
  fillchar(que,sizeof(que),0);
  v[s]:=true;l:=0;r:=1;
  que[l]:=s;
  while l<>r do
   begin
     u:=que[l];
     tmp:=last[u];
     while tmp<>-1 do
      begin
        if (e[tmp].w>0)and(not v[e[tmp].v]) then
         begin
           d[e[tmp].v]:=d[u]+1;
           que[r]:=e[tmp].v;
           inc(r);
           v[e[tmp].v]:=true;
         end;
        tmp:=e[tmp].pre;
      end;
     inc(l);
   end;
  exit(v[t]);
end;

function dfs(p,a,t:longint):longint;
var f,flow,tmp:longint;
begin
  if (p=t)or(a=0)then exit(a);
  flow:=0;
  tmp:=last[p];
  while tmp<>-1 do
   begin
     if (e[tmp].w>0)and(d[e[tmp].v]=d[p]+1)then
      begin
        f:=dfs(e[tmp].v,min(a,e[tmp].w),t);
        if f<>0 then
         begin
           dec(e[tmp].w,f);
           dec(a,f);
           inc(e[tmp xor 1].w,f);
           inc(flow,f);
           if a=0 then break;
         end;
      end;
     tmp:=e[tmp].pre;
   end;
  exit(flow);
end;

function dinic(s,t:longint):longint;
var ans:longint;
begin
  ans:=0;
  while bfs(s,t) do
    ans:=ans+dfs(s,maxlongint,t);
  exit(ans);
end;

procedure init;
var i,j,k,l:longint;
begin
  read(m,n);
  for i:=1 to m do read(pignum[i]);
  fillchar(last,sizeof(last),255);
  fillchar(pig,sizeof(pig),0);
  tot:=-1;
  for i:=1 to n do
   begin
     read(k);
     for j:=1 to k do
      begin
        read(l);
        inc(pig[l][0]);
        pig[l][pig[l][0]]:=i;
      end;
     read(k);
     addedge(i,n+1,k);
   end;
  for i:=1 to m do
   if pig[i][0]<>0 then
    begin
      addedge(0,pig[i][1],pignum[i]);
      for j:=2 to pig[i][0] do
      addedge(pig[i][j-1],pig[i][j],maxlongint);
    end;
  write(dinic(0,n+1));
end;

begin
  init;
end.


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

历史上的今天

评论

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

页脚

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