膜板题 ->排水沟poj1273 网络流弄了将近一个月，寒假玩v家去了导致信息竞赛进度不大，不过还是先总结一下吧

一些概念

一 网络流满足三个性质： 1 容量限制 每条边不能够提供大于其流量的边，（反向边要加上对应的增广流量是为了满足流量守恒） 2 对称性 f(u,v)=-f(v,u) 3 流量守恒 所有点的流入量等于流出量 通俗点说就是你不能从1号城市运3个冰球到2号，而运到2号的再传到3号城市的冰球变成了1个（好吧很意义不明）

二 增广路 能走的路一定是还有流量的路， 而增广路是从s->t还能多增加流的路。

三 交替路 二分图从一端到另一端，走一边到另一边再到原来的一边的非同一个顶点的路是交替路（比较通俗）

存图方式

用vector模拟邻接表

struct edge { int to,cap,rev; };

其中cap是剩余容量，rev是反向边（和刘汝佳方法不一样）推荐白书上那种 方便

关于两个模板，fulkerson（我老是打错成**）和dinic算法 我们先来说一下fulkerson算法吧

fulkerson算法

复杂度O(F|E|)

用dfs找增广路 为了不走回头路，我们使用数组标记 一条路能走当且仅当它的剩余容量大于0，那么我们只需要不断地沿着路dfs就行了，唯一注意的是，我们要在增广一条路后去掉对应的容量 并把反向边加上容量（根据容量守恒原则） 没什么很难的地方 代码 可以练好后交poj1273

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <vector> using namespace std; const int maxn=500; const int inf=0x3f3f3f3f; struct edge { int to; int cap,rev; void ini() { to=0; cap=0; rev=0; } }; vector<edge> g[maxn]; bool used[maxn]; int s,t,n,m; int ans=0; void addedge(int from,int to,int cap) { g[from].push_back((edge){to,cap,g[to].size()}); g[to].push_back((edge){from,0,g[from].size()-1}); } int dfs(int v,int t,int f) { if(v==t) return f; used[v]=true; for(unsigned i=0;i<g[v].size();i++) { edge &buffer=g[v][i]; if(!used[buffer.to] && buffer.cap>0) { int d; d=dfs(buffer.to,t,min(f,buffer.cap)); if(d>0) { g[v][i].cap-=d; g[buffer.to][buffer.rev].cap+=d; return d; } } } return 0; } int max_flow(int st,int ed) { ans=0; while(1) { memset(used,0,sizeof(used)); int buff=dfs(st,ed,inf); if(buff==0) return ans; else { ans+=buff; } } } int main() { while(scanf("%d%d",&m,&n)==2) { s=1; t=n; for(int i=0;i<maxn;i++) { g[i].clear(); } for(int i=0;i<m;i++) { int from; int to; int cap; scanf("%d%d%d",&from,&to,&cap); addedge(from,to,cap); } ans=max_flow(s,t); printf("%d\n",ans); } return 0; }

dinic算法

复杂度O(|V||V||E|)上界比较松

将图分层， 对于一个图，每一次增广一定有一条路会断（即没有剩余容量） 这时我们记一个dis 数组来记起点到各个点的距离（我们暂时只考虑所有cost为1的情况） 这样可以保证不对一条没用的边进行多次检查，节省了时间，其余与深搜类似

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <cctype> //手写队列 //AC using namespace std; const int maxn=5000000; const int inf=0x3f3f3f3f; struct edge { int to; int cap; int rev; }; vector<edge> g[maxn]; int dis[maxn]; int cur[maxn]; int q[maxn]; int s,t,n,m; int res=0; int readint() { char c; int ans=0; while(c=getchar()) { if(isdigit(c)) { ans=ans*10+c-'0'; } else c=getchar(); } return ans; } void addedge(int from,int to,int cap) { g[from].push_back((edge){to,cap,g[to].size()}); g[to].push_back((edge){from,0,g[from].size()-1}); } void bfs() { memset(dis,-1,sizeof(dis)); memset(q,0,sizeof(q)); int hd=0; int tl=0; q[hd]=s; dis[s]=0; while(hd<=tl) { int head=q[hd]; hd++; for(unsigned i=0;i<g[head].size();i++) { edge &e =g[head][i]; if(e.cap>0 && dis[e.to]<0) { dis[e.to]=dis[head]+1; tl++; q[tl]=e.to; } } } } int dfs(int v,int ed,int flow) { int f; if(v==ed) { return flow; } else { for(int &i=cur[v];i<g[v].size();i++)//注意这里要引用 { edge & e=g[v][i]; if(e.cap>0 && dis[e.to]==dis[v]+1) { f=dfs(e.to,ed,min(flow,e.cap)); if(f>0) { e.cap-=f; g[e.to][e.rev].cap+=f;//注意结构体后要带成员 return f; } } } } return 0; } int max_flow(int st,int ed) { int ans=0; while(1) { bfs(); if(dis[t]<0) return ans; else { memset(cur,0,sizeof(cur)); int f; while((f=dfs(st,ed,inf))>0) { ans+=f; } } } } int main() { scanf("%d%d%d%d",&n,&m,&s,&t); res=0; for(int i=0;i<maxn;i++) { g[i].clear(); } for(int i=0;i<m;i++) { int from; int to; int cap; scanf("%d%d%d",&from,&to,&cap); addedge(from,to,cap); } res=max_flow(s,t); printf("%d\n",res); return 0; }

二分图匹配的网络流变形

对于一个二分图，我们想到如果将最大匹配转化为最大流就好了。 那么如何转化呢？对于一个匹配，一定是数条没有公共顶点的边，那么就想到了数条这样相同流的增广路 我们添加一个源点和汇点，它们分别向两边的两点各连一条容量为1，cost=0的边，这样就转化为了最大流来求这些边的问题了

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <vector> //AC using namespace std; const int maxn=10000; const int inf=0x3f3f3f3f; int dis[maxn]; int cur[maxn]; int s,t,n,m,e; struct edge { int to,cap,rev; }; vector<edge > g[maxn]; void addedge(int from,int to,int cap) { g[from].push_back((edge){to,cap,g[to].size()}); g[to].push_back((edge){from,0,g[from].size()-1}); } //dinic bool bfs(int st,int ed) { memset(dis,inf,sizeof(dis)); int q[maxn]; int head=0; int tail=0; q[head]=st; dis[st]=0; while(head<=tail) { int h=q[head]; head++; for(unsigned i=0;i<g[h].size();i++) { edge &e=g[h][i]; if(e.cap>0 && dis[e.to]==inf) { dis[e.to]=dis[h]+1; tail++; q[tail]=e.to; } } } return (dis[ed]!=inf); } int dfs(int v,int ed,int leftflow) { if(leftflow==0 || v==ed) { return leftflow; } else { for(int &i=cur[v];i<g[v].size();i++) { edge & e=g[v][i]; if(e.cap>0 && dis[e.to]==dis[v]+1)/ { int f=dfs(e.to,ed,min(leftflow,e.cap)); if(f>0) { e.cap-=f;/// g[e.to][e.rev].cap+=f;/// return f; } } } return 0; } } int main() { scanf("%d%d%d",&n,&m,&e); s=0; t=n+m+1; memset(dis,inf,sizeof(dis)); memset(cur,0,sizeof(cur)); for(int i=0;i<maxn;i++) { g[i].clear(); } for(int i=0;i<e;i++) { int from; int to; scanf("%d%d",&from,&to); if(from>=1 && from<=n && to>=1 && to<=m) { to+=n; addedge(from,to,1); } } for(int i=1;i<=n;i++) { addedge(s,i,1); } for(int j=n+1;j<=n+m;j++) { addedge(j,t,1); } int ans=0; while(bfs(s,t)) { int f; memset(cur,0,sizeof(cur));/ while((f=dfs(s,t,inf))>0) { ans+=f; } } printf("%d\n",ans); return 0; }

固定流最小费用流问题

给你10个冰球，你要运完，但是你要经过长度最小的道路 如何做呢？这里推荐一个用连续最短路的贝尔曼福德实现的算法： 流固定，每次以最短路增广，从流中减去对应流 这样写看上去比较好懂的

int min_cost_flow(int st,int ed,int f) { int ans=0; while(f>0) { bool update=true; memset(dis,inf,sizeof(dis)); dis[st]=0; while(update) { update=false; for(int i=0;i<=n+m+1;i++) { if(dis[i]!=inf) { for(unsigned j=0;j<g[i].size();j++) { edge & e=g[i][j]; if(e.cap>0 && dis[e.to]>dis[i]+e.cost) { dis[e.to]=dis[i]+e.cost; prevv[e.to]=i; preve[e.to]=j; update=true; } } } } } if(dis[ed]==inf) { return -1; } int d=inf; for(int i=ed;i!=st;i=prevv[i]) { d=min(d,g[prevv[i]][preve[i]].cap); } f-=d; ans+=dis[ed]*d; for(int i=ed;i!=st;i=prevv[i]) { edge & e=g[prevv[i]][preve[i]]; e.cap-=d; g[i][e.rev].cap+=d; } } return ans; }

应用当然不止这些 最主要是建模，这里有些题（书上的例题） poj1273排水沟 poj3281奶牛的餐饮 poj3686玩具 luogu3386二分图匹配模板