首页 > 代码库 > 网络流建模
网络流建模
poj3281
有F种食物和D种饮料,每种食物或饮料只能供一头牛享用,且每头牛只享用一种食物和一种饮料。现在有N头牛,每头牛都有自己喜欢的食物种类列表和饮料种类列表,问最多能使几头牛同时享用到自己喜欢的食物和饮料。(1 <= F <= 100, 1 <= D <= 100, 1 <= N <= 100)
分析:
s和每种食物连边c=1
每种饮料和t连边c=1
然后牛拆成两个i1,i2放中间,喜欢的食物连i1,i2连喜欢的饮料c=1
代码:
program Dining; var c:array[0..1000,0..1000]of longint; q:array[0..3000]of longint; sz:array[0..1000]of longint; n,i,m,num,m1,m2,x,v1,v2,j:longint; function min(x,y:longint):longint; begin if x<y then min:=x else min:=y; end; function bfs:boolean; var h,t,x,i:longint; begin fillchar(sz,sizeof(sz),0); h:=0; t:=1; q[1]:=0; sz[0]:=1; while h<t do begin inc(h); x:=q[h]; for i:=0 to num do if (c[x,i]>0)and(sz[i]=0) then begin sz[i]:=sz[x]+1; inc(t); q[t]:=i; end; end; if sz[num]=0 then exit(false) else exit(true); end; function dfs(x,flow:longint):longint; var d,i:longint; begin if x=num then exit(flow); for i:=0 to num do if (sz[i]=sz[x]+1)and(c[x,i]>0) then begin d:=dfs(i,min(c[x,i],flow)); if d<>0 then begin inc(c[i,x],d); dec(c[x,i],d); exit(d); end; end; exit(0); end; procedure solve; var ans,s,flow,inf:longint; begin ans:=0; s:=0; inf:=maxlongint div 3; while bfs do begin flow:=dfs(s,inf); while flow<>0 do begin inc(ans,flow); flow:=dfs(s,inf); end; end; writeln(ans); end; begin assign(input,‘Dining.in‘); reset(input); assign(output,‘Dining.out‘); rewrite(output); readln(n,m1,m2); num:=n*2+m1+m2+1; for i:=1 to m1 do c[0,i+n*2]:=1; for i:=1 to m2 do c[i+m1+n*2,num]:=1; for i:=1 to n do c[i,i+n]:=1; for i:=1 to n do begin read(v1,v2); for j:=1 to v1 do begin read(x); x:=x+n*2; c[x,i]:=1; end; for j:=1 to v2 do begin read(x); x:=x+n*2+m1; c[i+n,x]:=1; end; readln; end; solve; close(input); close(output); end.
网络流建模
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。