首页 > 代码库 > 网络流
网络流
1. 最大流问题。
实现t点流量最大。这是网络流的基本问题。通常三种方法，EK，Dinic，ISAP。EK最好拍，但是每次找增广路都要BFS一次实在伤不 起，Dinic加上各种神神优化才赶得上没优化的ISAP，弃之。ISAP难拍难理解，但是花点时间理解一下就好了，主要是当前弧优化和GAP优化比较难 理解，以及ISAP的坑爹的反向BFS。
模板如下，采用LRJ的边表，我觉得其实挺好用的，相比于链式前向星。
HDU 1532（网络流各类拍法测试裸题）
#include "cstdio"#include "vector"#include "cstring"#include "queue"using namespace std;#define maxn 405#define inf 100000000struct Edge{ int from,to,cap,flow; Edge(int FROM,int TO,int CAP,int FLOW):from(FROM),to(TO),cap(CAP),flow(FLOW) {}};int d[maxn],p[maxn],gap[maxn],cur[maxn];bool vis[maxn];vector<int> G[maxn];vector<Edge> edges;int n,m;void addedge(int from,int to,int cap){ edges.push_back(Edge(from,to,cap,0)); edges.push_back(Edge(to,from,0,0)); int m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1);}void bfs(int s,int t){ memset(vis,false,sizeof(vis)); memset(d,0,sizeof(d)); memset(p,0,sizeof(p)); d[t]=0;vis[t]=true; queue<int> Q;Q.push(t); while(!Q.empty()) { int u=Q.front();Q.pop(); for(int v=0;v<G[u].size();v++) { Edge e=edges[G[u][v]^1]; if(!vis[e.from]&&e.cap>e.flow) { vis[e.from]=true; d[e.from]=d[u]+1; Q.push(e.from); } } }}int augment(int s,int t){ int x=t,a=inf; while(x!=s) { Edge e=edges[p[x]]; a=min(a,e.cap-e.flow); x=e.from; } x=t; while(x!=s) { edges[p[x]].flow+=a; edges[p[x]^1].flow-=a; x=edges[p[x]].from; } return a;}int maxflow(int s,int t){ int flow=0,u=s; bfs(s,t); memset(gap,0,sizeof(gap)); memset(cur,0,sizeof(cur)); for(int i=0;i<n;i++) gap[d[i]]++; while(d[s]<n) { if(u==t) { flow+=augment(s,t); u=s; } bool flag=false; for(int v=cur[u];v<G[u].size();v++) //Advance { Edge e=edges[G[u][v]]; if(e.cap>e.flow&&d[u]==d[e.to]+1) { flag=true; p[e.to]=G[u][v]; cur[u]=v; u=e.to; break; } } if(!flag) //Retreat { int m=n-1; for(int v=0;v<G[u].size();v++) { Edge e=edges[G[u][v]]; if(e.cap>e.flow) m=min(m,d[e.to]); } if(--gap[d[u]]==0) break; gap[d[u]=m+1]++; cur[u]=0; if(u!=s) u=edges[p[u]].from; } } return flow;}int main(){ //freopen("in.txt","r",stdin); int u,v,w; while(~scanf("%d%d",&m,&n)) { for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); } printf("%d\n",maxflow(1,n)); for(int i=0;i<maxn;i++) G[i].clear(); edges.clear(); }}
2. 最小割问题
你会在各种资料上见到maxflow<=mincut，最小割到底是个啥玩意呢。我们先来说说割吧，你可以把割理解成在图中所有引导至t点的直接弧或间接弧的总和，说白了就是对最终流量产生影响的有用弧（你要知道图中很多点是到不了t点的，这些点所连的弧是没用的，废弃的）。割的容量即所有有用弧的总容量，就是最大割啦。有了最大割就不难理解最小割了，最小割就是在割上走的流量最少呗，但是这最少可不能是0, 我们定义最小值就是在最大流前提下的最小走过流量，所以最大流=最小割。
最小割是个很蹩脚的定义，但是确能解决一类特殊的问题，这类问题统称最小割问题。
如vijos 1590, 初看上去像个费用流，其实不是。洪水堵截，在不到t点的情况下，你可以在途中任一点进行堵截，我们当然选择在费用最小的点把它堵上。等等，这不就是最大流问题么，想一想最大流的增广路，增广路的最大流量由路上最小的容量决定，我们不妨把费用设为容量，那么在费用最小点堵截不就相当于找条增广路么。这就是最小割建模，最小最小，不是指结果最小，而是过程最小，最大流和最小割是不矛盾滴。当然，这题的难度不止于此，费用在点上而不在弧上，所以我们要拆点，这叫拆点网络流。拆点的方法：开双倍点，本点连影子点（容量为费用，注意这题源汇无费用，源汇与影子点的容量为inf），对于u-v有连接的，u连v‘（容量为inf），v连u’（无向图，容量为inf）。然后，就是这题的判定条件，如果maxflow=0就是不存在割喽。maxflow>=inf，无法堵截。剩余就是能堵截了。最后，这题数据卡EK，EK只能过80%的点，所以还是乖乖拍ISAP吧。
vijos 1524, 和上题类似，还是堵截类问题。不过好在不用拆点了，但是却是多汇点（你可以认为犯人可以从汇点逃跑），所以对于所有汇点，向超级汇点连一条边即可(容量inf）。这题不卡EK。
hdu 4289, 又是堵截类问题，orz，貌似最小割这个蹩脚的定义只能解决这些堵截类问题了。拆点网络流，注意s，t都有权，拆的时候和笨笨熊区别开。继续加个超级汇即可。
UVA 11248，最大流/最小割的综合题。首先先让你判断是否能达到指定流量，增广到指定流量break即可。第二，如果不能达到指定流量，问你是否能修改一条边的容量，达到指定流量。第二步比较麻烦，首先修改的边至少得是割里面的，这是第一层剪枝。我用随机数据跑所有边，结果时间是10倍，说明这个剪枝很重要。其次，就是不要把流量清掉，直接继续从s增广，记得备份原始图，每次修改后覆盖回来。在其次，就是数据结构问题，如果你存图的数据结构支持重边（就是相同的边容量合并），那么这样就不用费事把割里边取出修改，直接加一条重边即可。还有个小注意点，虽说是不清流量，但是加边后重新增广的流量是多出的流量，而不是现有的总流量。
最麻烦的是割的记录问题，尤其是ISAP的记录，这里贴下LRJ的代码。反正我是没看懂orz。
vector<Edge> Mincut(LL s,LL t) // call this after maxflow{ BFS(s,t); vector<Edge> ans; for(int i = 0; i < edges.size(); i++) { Edge& e = edges[i]; if(!vis[e.from] && vis[e.to] && e.cap > 0) ans.push_back(e); } return ans;}
3. 最小费用流问题
你可以认为费用流=最大流+最短路径。原因是最小费用流的代码真的是这么写的。没有烦人的Dinic、ISAP，就是在EK的基础上改了一下， 毕竟最大流的增广路可以一次BFS，但是加上最短路，每次增广后图的结构就会改变，所以每次都得BFS。退化了orz。 但是代码简单不代表用起来简单，最小费用流的重点在于可以求解最优化问题，比如某些动态规划，俗称的2B网络流建图方式。网络流的精髓在于最小费用流，难 点就在建图上。
模板如下。
#include "cstdio"#include "vector"#include "cstring"#include "queue"using namespace std;#define maxn 210#define inf 99999999struct Edge{ int from,to,cap,flow,cost; Edge(int FROM,int TO,int CAP,int FLOW,int COST):from(FROM),to(TO),cap(CAP),flow(FLOW),cost(COST) {}};vector<int> G[maxn];vector<Edge> edges;int d[maxn],p[maxn],a[maxn];bool inq[maxn];void addedge(int from,int to,int cap,int cost){ edges.push_back(Edge(from,to,cap,0,cost)); edges.push_back(Edge(to,from,0,0,-cost)); int m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1);}bool spfa(int s,int t,int &flow,int &cost){ memset(p,-1,sizeof(p)); for(int i=s;i<=t;i++) d[i]=(i==s?0:inf); a[s]=inf; queue<int> Q;Q.push(s); while(!Q.empty()) { int u=Q.front();Q.pop(); inq[u]=false; for(int v=0;v<G[u].size();v++) { Edge e=edges[G[u][v]]; if(e.cap>e.flow&&d[u]+e.cost<d[e.to]) { d[e.to]=d[u]+e.cost; a[e.to]=min(a[u],e.cap-e.flow); p[e.to]=G[u][v]; if(!inq[e.to]) { inq[e.to]=true; Q.push(e.to); } } } } if(d[t]==inf) return false; flow+=a[t]; cost+=d[t]; //很多人这里写着a[t]*d[t]是很坑的，最早的费用=权*流量，但不是永远都是这个，当然对于cap=1就无所谓了。 int u=t; while(u!=s) { edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; u=edges[p[u]].from; } return true;}
@费用流与建模
POJ 2195 经典的匹配费用流问题，建模的方案如下： 超级源点连所有X元素（人），费用0，流量1。X-Y有边则连，费用为权，流量随意（1或inf皆可）。所有Y（房子）连超级汇点，费用0，流量1。
POJ2135 只能存在一个方向的无向图，求个环，费用最小。这题是HDU 1853的弱化版，只要一个环足矣。有种偷懒不拆点的建图方式，利用本题只能存在一个方向，建无向图，费用为cost，容量为1，超级源点连源点，费用0容量2,汇点连超级汇点，费用0容量2即可。等于从s出发向t增广上下两路增广（容量为2的含义），解决了成环问题。
HDU 1853 有向图多环了。先拆点，拆点的方式与点权拆点不同。如果u、v有边，u连v‘，费用cost，容量1。超级源连所有本点，超级汇连所有影子点，费用0，容量1。这里最关键的是把权加在这条边上，但是本点影子点却没有连接。画个图就清楚了，将本点作为入点，影子点作为出点，u连v’将费用从影子点带到汇点。最大流量是有意义的，代表几个点被访问了。flow=n才能保证所有点全访问过，否则输出-1.
网络流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。