#1：最大流(EK算法)
这个算法很简单，就是 BFS 找增广路，然后对其进行 增广
找？我们就从源点一直 BFS 走来走去，碰到汇点就停，然后增广（每一条路都要增广）。我们在 BFS 的时候就注意一下流量合不合法就可以了。
增广？其实就是按照我们找的增广路在重新走一遍。走的时候把这条路的能够成的最大流量减一减，然后给答案加上最小流量就可以了。注意在增广的同时建反向边，一遍给程序一个反悔的机会（消化自OI-WIKI）
CODE：以USACO 4.2.1 Drainage Ditches草地排水为例
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define min(x,y) x<y?x:y
using namespace std;
const int inf=0x7fffffff;
int res[205][205];
bool vis[205];
int pre[205];
int n,m;
bool bfs(int s,int t)
{
int p;
queue <int> q;
memset(pre,-1,sizeof(pre));
memset(vis,false,sizeof(vis));
pre[s]=s;
vis[s]=true;
q.push(s);
while(!q.empty())
{
p=q.front();
q.pop();
for(int i=1;i<=n;i++)
{
if(res[p][i]>0&&!vis[i])
{
pre[i]=p;
vis[i]=true;
if(i==t)return true;
q.push(i);
}
}
}
return false;
}
int EK(int s,int t)
{
int f=0,d,i;
while(bfs(s,t))
{
d=inf;
for(i=t;i!=s;i=pre[i])
d=d<res[pre[i]][i]? d:res[pre[i]][i];
for(i=t;i!=s;i=pre[i])
{
res[pre[i]][i]-=d;
res[i][pre[i]]+=d;
}
f+=d;
}
return f;
}
int main()
{
scanf("%d%d",&m,&n);
int u,v,w;
memset(res,0,sizeof(res));
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
res[u][v]+=w;
}
printf("%d\n",EK(1,n));
return 0;
}
#2：最大流(DINIC算法)
#2-1Dinic：现将图分层，然后dfs增广
CODE：以USACO 4.2.1 Drainage Ditches草地排水为例
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf=0x7fffffff;
int cnt=2;
int head[505];
int next[505];
int to[505];
int f[505];
int d[505];
void link(int u,int v,int w)
{
to[cnt]=v;
f[cnt]=w;
next[cnt]=head[u];
head[u]=cnt++;
}
queue <int> q;
bool bfs(int s,int t)
{
while(!q.empty())q.pop();
memset(d,0,sizeof(d));
d[s]=1;q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=next[i])
{
if(f[i]>0&&!d[to[i]])
{
d[to[i]]=d[u]+1;
q.push(to[i]);
}
}
}
while(!q.empty())q.pop();
if(!d[t])return false;
return true;
}
int dfs(int k,int t,int flow)
{
if(k==t)return flow;
for(int i=head[k];i;i=next[i])
{
if((d[to[i]]==d[k]+1)&&(f[i]!=0))
{
int dt=dfs(to[i],t,min(flow,f[i]));
if(dt>0)
{
f[i]-=dt;
f[i^1]+=dt;
return dt;
}
}
}
return 0;
}
int dinic(int s,int t)
{
int ans=0;
while(bfs(s,t))
{
while(int d=dfs(s,t,inf))
ans+=d;
}
return ans;
}
int main()
{
int m,n;
scanf("%d%d",&m,&n);
int u,v,w;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
link(u,v,w);link(v,u,0);
}
printf("%d\n",dinic(1,n));
return 0;
}
#2-2多路增广：在dfs时，记一个used为当前剩余容量，没留完就继续流。
CODE：以USACO 4.2.1 Drainag Ditches 草地排水（数据加强）为例
DFS：部分
int dfs(int k,int t,int flow)
{
if(k==t)return flow;
int used=flow;
for(int i=head[k];i&&used;i=next[i])
{
int y=to[i];
if(d[y]==d[k]+1&&f[i])
{
int dt=dfs(y,t,min(used,f[i]));
if(!dt) d[y]=0;
used-=dt,f[i]-=dt,f[i^1]+=dt;
}
}
return flow-used;
}
#2-3当前弧优化：先复制一遍head到cur中，然后每次从cur枚举，把枚举过的边删掉
CODE：以USACO 4.2.1 Drainage Ditches(数据加强)草地排水为例（同时加两个优化）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf=0x7fffffff;
int cnt=2;
int m,n;
int head[2000005];
int cur[2000005];
int next[2000005];
int to[2000005];
int f[2000005];
int d[2000005];
void link(int u,int v,int w)
{
to[cnt]=v;
f[cnt]=w;
next[cnt]=head[u];
head[u]=cnt++;
}
bool bfs(int s,int t)
{
queue <int> q;
for(int i=1;i<=n;i++)
{
cur[i]=head[i];
d[i]=0;
}
d[s]=1;q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=next[i])
{
if(f[i]>0&&!d[to[i]])
{
d[to[i]]=d[u]+1;
q.push(to[i]);
}
}
}
if(!d[t])return false;
return true;
}
int dfs(int k,int t,int flow)
{
if(k==t)return flow;
int used=flow;
for(int i=cur[k];i&&used;i=next[i])
{
cur[k]=i;
int y=to[i];
if(d[y]==d[k]+1&&f[i])
{
int dt=dfs(y,t,min(used,f[i]));
if(!dt) d[y]=0;
used-=dt,f[i]-=dt,f[i^1]+=dt;
}
}
return flow-used;
}
int dinic(int s,int t)
{
int ans=0;
while(bfs(s,t))
{
while(int d=dfs(s,t,inf))
ans+=d;
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
int u,v,w;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&u,&v,&w);
link(u,v,w);link(v,u,0);
}
printf("%d\n",dinic(1,m));
return 0;
}
#3：最小割
#3-1：最大流最小割定理：最大流的值等于最小割的容量
#3-2：证明本蒟还不会，以下内容转自OI WIKI：
定理：f(s,t)max=f(s,t)min
对于任意一个可行流f(s,t)的割 (S,T)，我们可以得到：f(s,t)=出边的总流量－入边的总流量≤出边的总流量=c(s,t)
如果我们求出了最大流 f，那么残余网络中一定不存在s到t的增广路经，也就是s的出边一定是满流，s的入边一定是零流，于是有：f(s,t)=出边的总流量－入边的总流量≤出边的总流量=c(s,t)
结合前面的不等式，我们可以知道此时f已经达到最大。
#3-3：方案（转自OI WIKI）：
我们可以通过从源点s开始 DFS，每次走残量大于0的边，找到所有S点集内的点。
CODE：（转自OI WIKI）
void dfs(int u) {
vis[u] = 1;
for (int i = lnk[u]; i; i = nxt[i]) {
int v = ter[i];
if (!vis[v] && val[i]) dfs(v);
}
}
#4：费用流(SSP算法)
SSP算法=把EK/DINIC的BFS换成SPFA
模板代码：(EK)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf=0x7fffffff;
int cnt=2;
int head[2000005];
int nt[2000005];
int to[2000005];
int f[2000005];
int c[2000005];
int d[2000005];
int dis[2000005];
int vis[2000005];
int pre[2000005];
void link(int u,int v,int w,int z)
{
to[cnt]=v;
f[cnt]=w;
c[cnt]=z;
nt[cnt]=head[u];
head[u]=cnt++;
}
bool spfa(int s,int t)
{
queue <int> q;
memset(dis,0x3f,sizeof(dis));
memset(pre,-1,sizeof(pre));
memset(vis,0,sizeof(vis));
dis[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty())
{
int now=q.front();
vis[now]=0;
q.pop();
for(int i=head[now];i;i=nt[i])
{
int go=to[i],fw=f[i];
if(fw>0&&dis[go]>dis[now]+c[i])
{
dis[go]=dis[now]+c[i];
pre[go]=i^1;
if(!vis[go])
{
vis[go]=1;
q.push(go);
}
}
}
}
return pre[t]!=-1;
}
void EK(int s,int t,int &maxflow,int &mincost)
{
maxflow=mincost=0;
while(spfa(s,t))
{
int ll=inf;
for(int i=pre[t];i!=-1;i=pre[to[i]])
{
ll=min(ll,f[i^1]);
}
for(int i=pre[t];i!=-1;i=pre[to[i]])
{
f[i]+=ll;
f[i^1]-=ll;
}
maxflow+=ll;
mincost+=ll*dis[t];
}
}
int main()
{
int m,n,s,t,ans1,ans2;
scanf("%d%d%d%d",&n,&m,&s,&t);
int u,v,w,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&u,&v,&w,&z);
link(u,v,w,z);link(v,u,0,-z);
}
EK(s,t,ans1,ans2);
printf("%d %d",ans1,ans2);
return 0;
}
eagle's blog 