我做最大流的第一道题 ; )

最大流

最大流de思路就酱

分层：

把各个点点分层。把  原点  到各个点  的路上  需要经过几个点  全部算出来，然后把一样的分在同一层。

像酱：

分层（这张有点丑，回头改好看一点）

AND最好用  宽度优先搜索

上代码

procedure bfs;

VAR i,x:longint;

begin

for i:=2 to n do

begin

dis[i]:=-1;

end;

dis[1]:=0;

head:=1;

tail:=1;

q[1]:=1;

while head<=tail do

begin

x:=q[head];

for i:=1 to n do

begin

if flow[x,i]>0 then

begin

if dis[i]<0 then

begin

dis[i]:=dis[x]+1;

inc(tail);

q[tail]:=i;

end;

end;

end;

inc(head);

end;

end;

找一条路径  &  各种处理：

什么样的路径呢？

从原点到终点（也叫汇点）的  一条  路径。

真的只要  一条  ！！！

找到  一条  从原点到终点的路径，然后把这一条路上  每两个点之间的流量  都减去  这一路上最小的那个流量。

或者说，找到  这一路上  最小的那个流量  ，  然后把  每两个点之间的流量  都减去  这个流量。

然后，在它的  反向弧  上加上这个最小流量。

什么是  反向弧  ？

一条边  的反过来的  那一条边就是  反向弧  。比如  有一条边  从 1 到 2  ，那么它的  反向弧  就是  从 2 到 1  。同时  从2到1  这条边的反向弧正是  从 1 到 2  这条边。  反向弧   是相对的。它的作用是让电脑有一个 “ 后悔 ” 的机会。反正我也不知道为什么要加  反向弧  。（  反向弧  也是可以走的啊！！！）

也就是如果  从 1 到 2  这条边  减去这个最小流量， 那么  从 2 到 1  就要加上这个最小流量。

话说，但一条边的  流量变为 0  的时候，这条边就  废了  ，  不能走了  。

上代码

function dfs(x,mx:longint):longint;//x 指当前跑到底几个点上， mx 指从从原点到现在这个点上最小的那个流量

VAR i,k:longint;

begin

if x=n then

begin

exit(mx);

end;

for i:=1 to n do

begin

if flow[x,i]>0 then

begin

if dis[i]=dis[x]+1 then

begin

if flow[x,i]>mx then// 从 x 到 i 是否比最小的流量还小，是的话更新一下

begin

k:=dfs(i,mx);// 进入下一个点，到时就能返回  整条路径上  的  最小流量  

end

else

begin

k:=dfs(i,flow[x,i]);

end;

flow[x,i]:=flow[x,i]-k;

flow[i,x]:=flow[i,x]+k;//  反向弧  的操作

if k>0 then// 当k>0的时候，说明已经找到  一条  路径，所以就要退出。

begin

exit(k);

end;

end;

end;

end;

exit(0);

end;

重复：

重复上面两个步骤，一直到再也找不到一条从原点到终点的路径了。答案就是  每条从原点到终点路径 的  那个最小流量  的和。

上代码

while true do// 无限循环，直到跳出

begin

bfs;// 分层

if dis[n]<0 then// 再也找不到一条从原点到终点的路径，那就跳出

begin

break;

end;

z:=dfs(1,maxint);// z 记录这整条路径上的那个  最小的流量

ans:=ans+z;// 答案 ; )

end;

草地排水

基本上把不用怎么修改代码就可以了。链接：(●—●) |1993 草地排水 | CODEVS, 算法爱好者社区

题目描述 Description

在农夫约翰的农场上，每逢下雨， Bessie 最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。

农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。

根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。

输入描述 Input Description

第1行: 两个用空格分开的整数 N (0 <= N <= 200) 和 M (2 <= M <= 200)。 N 是农夫 John 已经挖好的排水沟的数量， M 是排水沟交叉点的数量。交点 1 是水潭，交点 M 是小溪。

第二行到第N+1行: 每行有三个整数，Si, Ei, 和 Ci。Si 和 Ei (1 <= Si, Ei <= M) 指明排水沟两端的交点，雨水从 Si 流向 Ei。Ci (0 <= Ci <= 10,000,000) 是这条排水沟的最大容量。

输出描述 Output Description

输出一个整数，即排水的最大流量。

样例输入 Sample Input

5 4

1 2 40

1 4 20

2 4 20

2 3 30

3 4 10

样例输出 Sample Output

50

基本上就是根据  最大流  算法出的题。

上代码

VAR dis:array[0..200]of longint;// 记录分层图

flow:array[0..200,0..200]of longint;// 记录每两个点之间的流量

q:array[0..1000]of longint;// 分层（ procedure bfs ）中要用到的队列

i,m,n,s,t,c,head,tail,ans,z:longint;

procedure bfs;

VAR i,x:longint;

begin

fori:=2 to n do

begin

dis[i]:=-1;

end;

dis[1]:=0;

head:=1;

tail:=1;

q[1]:=1;

while head<=tail do

begin

x:=q[head];

for i:=1 to n do

begin

if flow[x,i]>0 then

begin

if dis[i]<0 then

begin

dis[i]:=dis[x]+1;

inc(tail);

q[tail]:=i;

end;

end;

end;

inc(head);

end;

end;

function dfs(x,mx:longint):longint;

VAR i,k:longint;

begin

ifx=n then

begin

exit(mx);

end;

fori:=1 to n do

begin

if flow[x,i]>0 then

begin

if dis[i]=dis[x]+1 then

begin

if flow[x,i]>mx then

begin

k:=dfs(i,mx);

end

else

begin

k:=dfs(i,flow[x,i]);

end;

flow[x,i]:=flow[x,i]-k;

flow[i,x]:=flow[i,x]+k;

if k>0 then

begin

exit(k);

end;

end;

end;

end;

exit(0);

end;

begin

read(m,n);

fori:=1 to m do

begin

read(s,t,c);

flow[s,t]:=flow[s,t]+c;

end;

while true do

begin

bfs;

if dis[n]<0 then

begin

break;

end;

z:=dfs(1,maxint);

ans:=ans+z;

end;

writeln(ans);

end. 

放到这上面来居然就没缩进了！！！

Ps:

谢谢同学的帮助，我才打出了上面的代码 ; )

内容全部原创 ; )