网络流入门题目
Program P1273;
Var
n,m,i,j,x,y,p,level:longint;
map,f:array[1..400,1..400] of longint;
list:array[0..400,0..400] of longint;
queue:array[1..400] of longint;
b:array[1..400] of boolean;
d,e:array[1..400] of longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure dijstra;
var
h,t,i:longint;
begin
queue[1]:=n;
b[n]:=true;
h:=1;
t:=1;
while h<=t do
begin
for i:=1 to n-1 do
if (map[i,queue[h]]>0) and (not(b[i])) then
begin
inc(t);
queue[t]:=i;
b[i]:=true;
d[i]:=d[queue[h]]+1;
end;
inc(h);
end;
d[1]:=n+1;
end;
procedure push(i,j:longint);
var
flow:longint;
begin
flow:=min(map[i,j]-f[i,j],e[i]);
if (e[j]=0) and (j<>1) and (j<>n) then
begin
inc(list[d[j],0]);
list[d[j],list[d[j],0]]:=j;
level:=max(level,d[j]);
end;
dec(e[i],flow);
inc(e[j],flow);
inc(f[i,j],flow);
f[j,i]:=-f[i,j];
end;
procedure relable(i:longint);
var
j,minj:longint;
begin
minj:=maxlongint;
for j:=1 to n do
if (map[i,j]-f[i,j]>0) and (b[j]) then
minj:=min(minj,d[j]);
d[i]:=minj+1;
level:=d[i];
list[level,0]:=1;
list[level,1]:=i;
end;
procedure sa;
var
i,j,minj:longint;
tag:boolean;
begin
dijstra;
level:=0;
for i:=1 to n do
if (map[1,i]>0) and (b[i]) then
begin
dec(e[1],map[1,i]);
inc(e[i],map[1,i]);
inc(f[1,i],map[1,i]);
f[i,1]:=-f[1,i];
inc(list[d[i],0]);
list[d[i],list[d[i],0]]:=i;
level:=max(level,d[i]);
end;
while (level>0) do
begin
i:=list[level,list[level,0]];
dec(list[level,0]);
while (level>0) and (list[level,0]=0) do dec(level);
for j:=1 to n do
if (map[i,j]-f[i,j]>0) and (d[i]=d[j]+1) and (b[j]) then
begin
push(i,j);
if e[i]=0 then break;
end;
if e[i]>0 then relable(i);
end;
end;
begin
while not eof do
begin
fillchar(map,sizeof(map),0);
fillchar(f,sizeof(f),0);
fillchar(d,sizeof(d),0);
fillchar(b,sizeof(b),false);
fillchar(list,sizeof(list),0);
fillchar(e,sizeof(e),0);
readln(m,n);
for i:=1 to m do
begin
readln(x,y,p);
inc(map[x,y],p);
end;
sa;
writeln(e[n]);
end;
end.
分享到:
相关推荐
很经典的图论,网络流入门的题目,值得一看啊~~其中有简单的解析
这题是道神题,神就神在,它既能让你搞懂网络流及其优化,还给了你很大的优化空间。
最短增广路算法的实现 并加上了gap优化和当前弧优化 代码为POJ3469(dual core)的源码
4.图论 //Dijkstra、最小生成树、网络流 5.数论 //解模线性方程 6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7.组合数学 //Polya定理 8.模拟 9.数据结构 //并查集、堆 10.博弈论 //表示举例 非主流...
Dinic多路增广pascal源码 poj 1273格式
一个有关网络流的课件,还是不错的,值得学习一下
3.2.2 IntServ流类型 34 3.2.3 RSVP 34 3.2.4 其他的RSVP和集成服务方案 36 3.3 差分服务 37 3.3.1 DiffServ的模型和操作 37 3.3.2 DS字节的格式 39 3.4 IP安全性 40 3.4.1 IPsec安全关联 41 3.4.2 鉴权头和封装安全...
4.1 最大乘积问题 4.2 魔术数字游戏 4.3 Jimmy's Bad Day 5.1 循环赛的日程表问题 5.2 猴子选大王 5.3 售货员的难题 6.1 最大字段和问题 6.2 N*N方阵 6.3 埃及分数最好表达式
8.10 最大网络流 175 8.11 最小费用流 180 8.12 最大团问题 182 8.13 二分图匹配 184 8.14 带权的最优二分图匹配 184 9.搜索算法概略 187 9.1 迭代深搜+IDA* 187 9.2 分之界限法(深搜) 189 9.3 A* 8数码问题( ...
4.图论 //Dijkstra、最小生成树、网络流 5.数论 //解模线性方程 6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7.组合数学 //Polya 定理 8.模拟 9.数据结构 //并查集、堆 10.博弈论 1、 排序 2、 搜索、回溯、...
3.5 借助水流解决问题的网络流 3.5.1 最大流 3.5.2 最小割 3.5.3 二分图匹配 3.5.4 一般图匹配 3.5.5 匹配、边覆盖、独立集和顶点覆盖 3.5.6 最小费用流 3.5.7 应用问题 3.6 与平面和空间打交道的计算几何 3.6.1 ...
leetcode中国功夫 现状 (2011.11.19) poj: 顶级编码器: 代码力量: 间谍: 佐伊: 福伊: 紫外线: ltOJ: leetcode: ...网络流问题 算法评论(中文)感谢七月的博客 高级数据结构: HZ @ UCSD CSE