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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【网络流24题】【二分图多重匹配】【圆桌问题】  

2014-01-25 14:50:56|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   归纳题意就是有N个点集,每一个点集有Ri个点,然后要求把这些点再重新划分成M个点集,每个点集中不存在两个点使得它们来自一个点集,求分配方案,若无解输出0。
   首先咱们得考虑网络流的内涵是什么...实际上就是每一个餐桌每一个代表团最多一个人去,就是说我们可以把餐桌看成节点,然后代表团看成另一个节点,每一个节点连一条容量为1的边,把人看做流量,那么最多只允许一个人去就实现了。然后我们把源点与代表团相连,每条边容量为代表团的人数,然后汇点与餐桌相连,每条边容量为其容纳人数,那么一个可行流就是一种方案,我们跑一遍最大流,检测它的大小是否与餐桌总容量相同,如果不相同显然无解,否则从代表团依次扫过去,输出相连的残余网络为0的餐桌为答案即可。这里发现其实咱们可以一开始初始化时所有边标记为-1,就不用DFS了...
   注意初始化为-1的时候反向边还是要赋值为0!....
   对于这一题的本质模型,实际上是二分图中的左边每个点可以和多个点匹配,给定左边点和右边点的最多匹配次数,求最大匹配的问题,也叫 二分图多重匹配问题
===================================================================

program table;
const maxn=500;
var g:array[0..maxn,0..maxn]of longint;
    que,d:array[0..maxn]of longint;
    v:array[0..maxn]of boolean;
    n,m:longint;

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

function bfs(s,t:longint):boolean;
var i,u,l,r:longint;
begin
  fillchar(que,sizeof(que),0);
  fillchar(v,sizeof(v),false);
  fillchar(d,sizeof(d),0);
  l:=0;r:=1;que[l]:=s;v[s]:=true;
  while l<r do
   begin
     u:=que[l];
     for i:=0 to n+m+1 do
      if (g[u][i]>0)and(not v[i]) then
        begin
          que[r]:=i;
          inc(r);
          d[i]:=d[u]+1;
          v[i]:=true;
        end;
     inc(l);
   end;
  exit(v[t]);
end;

function dfs(p,a,t:longint):longint;
var f,flow,i:longint;
begin
  if (p=t)or(a=0) then exit(a);
  flow:=0;
  for i:=0 to n+m+1 do
   if (g[p][i]>0)and(d[i]=d[p]+1)then
    begin
      f:=dfs(i,min(g[p][i],a),t);
      if f=0 then continue;
      inc(flow,f);
      inc(g[i][p],f);
      dec(g[p][i],f);
      dec(a,f);
      if a=0 then break;
    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,tot1,tot2,tot3:longint;
begin
  read(n,m);
  fillchar(g,sizeof(g),255);
  tot1:=0;tot2:=0;
  for i:=1 to n do
    for j:=1 to m do
      begin
        g[i][j+n]:=1;
        g[j+n][i]:=0;
      end;
  for i:=1 to n do
   begin
     read(j);
     g[0][i]:=j;
     g[i][0]:=0;
     tot1:=tot1+j;
   end;
  for i:=1 to m do
   begin
     read(j);
     g[i+n][n+m+1]:=j;
     g[n+m+1][i+n]:=0;
     tot2:=tot2+j;
   end;
  if tot2<tot1 then begin write(0);exit;end;
  tot3:=dinic(0,n+m+1);
  if tot3<>tot1 then begin write(0);exit;end;
  writeln(1);
  for i:=1 to n do
   begin
    for j:=1 to m do
      if g[i][j+n]=0 then write(j,' ');
    writeln;
   end;
end;

begin
  assign(input,'table9.in');reset(input);
  assign(output,'f.out');rewrite(output);
  init;
  close(input);close(output);
end.


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

历史上的今天

评论

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

页脚

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