网络流入门题目
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.
Sap：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cstdlib>
#include<cstring>
using namespace std;
#define MAXN (200000+10)
#define MAXNnode (200000+10)
#define MAXedge (200000+10)
#define INF (2139062143)
int n,m,size,edge[MAXedge],pre[MAXNnode],next[MAXedge],weight[MAXedge],s,t;
int un(int p){return (p%2)?(p+1):p-1;}
void addedge(int u,int v,int w)
{
edge[++size]=v;weight[size]=w;
next[size]=pre[u];pre[u]=size;
edge[++size]=u;weight[size]=0;
next[size]=pre[v];pre[v]=size;
}
int q[MAXN*10],d[MAXN*2],pre2[MAXN],cnt[MAXN];
void spfa()
{
int head=1,tail=1;
memset(d,127,sizeof(d));
q[1]=t;d[t]=0;
while (head<=tail)
{
int &u=q[head];
for (int p=pre[u];p;p=next[p])
{
int &v=edge[p];
if (d[v]>d[u]+1)
{
d[v]=d[u]+1;
q[++tail]=v;
cnt[d[v]]++;
}
}
head++;
}
}
int relable(int u)
{
int minj=n;
for (int p=pre[u];p;p=next[p])
if (weight[p]&&d[edge[p]]!=INF) minj=min(minj,d[edge[p]]+1);
return minj;
}
long long sap()
{
spfa();
int now=s;
long long nowflow=INF,maxflow=0;
while (1)
{
int flag=0;
for (int p=pre[now];p;p=next[p])
{
int &v=edge[p];
if (weight[p]&&d[v]==d[now]-1)
{
flag=v;
pre2[v]=p;
now=v;
break;
}
}
if (flag)
{
if (now==t)
{
nowflow=INF;
for (int p=now;p!=s;p=edge[un(pre2[p])])
nowflow=min(nowflow,(long long )weight[pre2[p]]);
maxflow+=nowflow;
for (int p=now;p!=s;p=edge[un(pre2[p])])
{
weight[pre2[p]]-=nowflow;
weight[un(pre2[p])]+=nowflow;
}
now=s;
memset(pre2,0,sizeof(pre2));
}
}
else
{
if (--cnt[d[now]]==0) break;
d[now]=relable(now);
cnt[d[now]]++;
if (now!=s) now=edge[un(pre2[now])];
}
}
return maxflow;
}
int main()
{
while (scanf("%d%d",&m,&n)==2)
{
memset(pre,0,sizeof(pre));
memset(next,0,sizeof(next));
memset(edge,0,sizeof(edge));
memset(weight,0,sizeof(weight));
memset(cnt,0,sizeof(cnt));
size=0; s=1;t=n;
for (int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
addedge(u,v,w);
}
if (m==0) cout<<'0'<<endl;
else cout<<sap()<<endl;
}
return 0;
}