网络流学习笔记

网络流问题，主要是给你一张网络，让你所流的水量最大。

主要用于求最大流问题。

网络流的相关定义：

源点：有n个点，有m条有向边，有一个点很特殊，只出不进，叫做源点。
汇点：另一个点也很特殊，只进不出，叫做汇点。
容量和流量：每条有向边上有两个量，容量和流量，从i到j的容量通常用c[i,j]表示,流量则通常是f[i,j].

通常可以把这些边想象成道路，流量就是这条道路的车流量，容量就是道路可承受的最大的车流量。很显然的，流量<=容量。而对于每个不是源点和汇点的点来说，可以类比的想象成没有存储功能的货物的中转站，所有“进入”他们的流量和等于所有从他本身“出去”的流量。

最大流：把源点比作工厂的话，问题就是求从工厂最大可以发出多少货物，是不至于超过道路的容量限制，也就是，最大流。

求解思路：

(1).寻找增广路的时候我们可以简单的从源点开始做BFS，并不断修改这条路上的delta 量，直到找到源点或者找不到增广路。
(2).在程序实现的时候，我们通常只是用一个c 数组来记录容量，而不记录流量，当流量+delta 的时候，我们可以通过容量-delta 来实现，以方便程序的实现。

为什么要建反向边？退流操作，如果在寻找增光路时需要回流，可以利用反向边进行回流

操作步骤：　

现用bfs寻找增光路，如果可以寻找到，则dfs求值

代码（dinic）

 1 #include<bits/stdc++.h>
 2 #define N 10000010
 3 using namespace std;
 4 struct edge
 5 {
 6     int now,next,to,f;
 7 }e[N];
 8 int n,m,head[N],lev[N],cur[N],tot=1,st,en;
 9 inline void add(int x,int y,int z)
10 {
11     e[++tot].next=head[x];
12     head[x]=tot;
13     e[tot].now=x;
14     e[tot].to=y;
15     e[tot].f=z;
16 }
17 inline int bfs()
18 {
19     queue<int>q;
20     memset(lev,0,sizeof(lev));
21     q.push(st);
22     lev[st]=1;
23     while(!q.empty())
24     {
25         int u=q.front();
26         q.pop();
27         for(int i=head[u];i!=-1;i=e[i].next)
28         {
29             int v=e[i].to;
30             if(lev[v]==0 && e[i].f)
31             {
32                 lev[v]=lev[u]+1;
33                 q.push(v);
34             }
35         }
36     }
37     return lev[en];
38 }
39 int dfs(int now,int a)
40 {
41     if(now == en || a<=0)
42         return a;
43     int flow=0,fl;
44     for(int &i=cur[now];i!=-1;i=e[i].next)
45     {
46         int v=e[i].to;
47         if(e[i].f && lev[v]==lev[e[i].now]+1)
48         {
49             fl=dfs(e[i].to,min(a,e[i].f));
50             e[i].f-=fl;
51             e[i^1].f+=fl;
52             flow+=fl;
53             a-=fl;
54             if(a<=0)
55                 break;
56         }
57     }
58     return flow;
59 }
60 void dinic()
61 {
62     int ans=0;
63     while(bfs())
64     {
65         for(int i=1;i<=n;i++)cur[i]=head[i];
66         ans+=dfs(st,0x7fffffff);
67     }
68     cout<<ans;
69 }
70 int main()
71 {
72     memset(head,-1,sizeof(head));
73     cin >> n >> m >> st >> en;
74     for(int i=1;i<=m;i++)
75     {
76         int a,b,c;
77         cin >> a >> b >> c;
78         add(a,b,c);
79         add(b,a,0);
80     }
81     dinic();
82     return 0;
83 }

View Code

模板题

网络流学习笔记

推荐阅读