网络流算法主要有两方面问题：

1、最大流 2、最小费用最大流

一、 最大流

https://www.cnblogs.com/ZJUT-jiangnan/p/3632525.html

先要理解一下反向边，然后以下是在他的基础上的三种方法

1、ff算法

dfs来找增广路 和下面代码其实是一样的

2、edmonds-Karp版本（EK算法）

用bfs来找增广路

import java.math.BigInteger; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; class Main{ public static void main(String[] args) { ek(); } static int ek(int s,int t){ int new_flow = 0; int max_flow = 0; while(new_flow!=0){ new_flow = find_path_bfs(s,t); update_residual_network(t,new_flow); max_flow+= new_flow; } return max_flow; } static int max = 10; static int INF = Integer.MAX_VALUE; static int m; static int [][]map; static int[] visited = new int[max]; static int[] pre = new int[max]; static int find_path_bfs(int s,int t){ visited = new int[max]; pre = new int[-1]; visited[s] = 1; int min = INF; Queue<Integer> q = new LinkedList<>(); ((LinkedList<Integer>) q).push(s); while (!q.isEmpty()){ int cur = q.poll(); if(cur==t){ break; } for(int i = 1;i<=m;i++){ if(visited[i]==0 && map[cur][i]!=0){ ((LinkedList<Integer>) q).push(i); min = Math.min(min,map[cur][i]); pre[i] = cur; visited[i] = 1; } } } if(pre[t]==-1) return 0; //他前面没有？？ return min; } static int update_residual_network(int u,int flow){ while (pre[u]!=-1){ map[pre[u]][u]-=flow; map[u][pre[u]]+=flow; u = pre[u]; } } }

3、dinic算法

根据残量网络计算层次图。 在层次图中使用DFS进行增广直到不存在增广路 重复以上步骤直到无法增广 参考：https://mp.weixin.qq.com/s/XlX1_JazHdMbX5-ToCGmgg

import java.util.*; public class fourth { static int n; static int m; static int s; static int t; static int[][] map = new int[10009][10009]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); s = sc.nextInt(); t= sc.nextInt(); for(int i = 1;i<=m;i++){ int u,v,w; u = sc.nextInt(); v = sc.nextInt(); w = sc.nextInt(); add(u,v,w); } System.out.println(dinic(s,t)); } static int INF = Integer.MAX_VALUE; static int[] visited= new int[10009]; static List<H> v[] = new LinkedList[10009]; static void init(){ for(int i= 0;i<v.length;i++){ v[i] = new LinkedList<H>(); } } static class H{ int to,cap,rev; public H(int to, int cap, int rev) { this.to = to; this.cap = cap; this.rev = rev; } } static void add(int f,int t ,int c){ v[f].add(new H(t,c,v[t].size()));//而且是f add t。size v[t].add(new H(f,0,v[f].size()-1)); } static int dinic(int s,int t){ int flow = 0; while (bfs(s,t)){ while (true){ int d = dfs(s,t,Integer.MAX_VALUE); if(d==0) break; flow+= d; } } return flow; } static int[] dep = new int[10009]; static boolean bfs(int s,int t){ init(); for (int i = 0;i<dep.length;i++){ dep[i] = -1; } Queue<Integer> que = new LinkedList<>(); while (!que.isEmpty()) que.poll(); //清空一下 ((LinkedList<Integer>) que).add(s); dep[s] = 0; while (!que.isEmpty()){ int k =((LinkedList<Integer>) que).pollFirst(); for(int i = 0;i<v[k].size();i++){ H node = v[k].get(i); if(dep[node.to]==-1 && node.cap>0){ dep[node.to] =dep[k]+1; ((LinkedList<Integer>) que).add(node.to); } } } return dep[t]!=-1; } static int dfs(int s,int t,int f){ int d = 0; if(s ==t) return f; for(int i = 0;i<v.length;i++){ H node = v[s].get(i); if((node.cap>0) && (dep[node.to] == dep[s]+1)){ d = dfs(node.to,t,Math.min(f,node.cap)); if (d!=0){ v[s].get(i).cap-=d; v[node.to].get(node.rev).cap+=d; return d; } } } return 0; } }

这里有一个小小的应用是二分图匹配，可以用dinic做，但是并不是很快，所以可以用匈牙利算法来做 原文章 https://mp.weixin.qq.com/s/9Koj65-zLZLtAk8h28nrWw

Sample Input

6 3 3

1 1

1 2

1 3

2 1

2 3

3 1

0

Sample Output

3 第一、増广是怎么走的呢，是从一个未匹配点出发 然后非匹配边 匹配边 非匹配边 一直这么交错着走的，最后一条边没有参与匹配,并且始点和终点还没 有被选择过.这样交错进行, 如果代码有看不懂可以参考这个文章，带进去想一下 https://mp.weixin.qq.com/s/HT6_GGPXexQ6eYjVdKlQLw?client=tim&ADUIN=1691439978&ADSESSION=1560154671&ADTAG=CLIENT.QQ.5603_.0&ADPUBNO=26882

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=1e3+10; int n1,n2,k; //n1,n2为二分图的顶点集，其中x属于n1，y属于n2 int map[maxn][maxn],vis[maxn],link[maxn]; //link记录n2中的点y在n1中所匹配的x点的编号 void init() { memset(map,0,sizeof map); memset(link,0,sizeof link); } int find(int x) { for(int i=1;i<=n2;i++) { if(map[x][i]&&!vis[i])//x->i有边，且节点i未被搜索 { vis[i]=1;//标记节点已经被搜索 //如果i不属于前一个匹配M，或被i匹配到的节点可以寻找到增广路 if(link[i]==0||find(link[i])) { link[i]=x;//更新 return 1;//匹配成功 } } } return 0; } int main() { while(~scanf("%d",&k)&&k){ scanf("%d%d",&n1,&n2); init(); for(int i=0;i<k;i++) { int x,y; scanf("%d%d",&x,&y); map[x][y]=1; } int ans=0; for(int i=1;i<=n1;i++) { memset(vis,0,sizeof vis); if(find(i)) ans++; } printf("%d\n",ans); } return 0; }

二、 最小费用最大流

就是把bfs换成spfa 最短路问题：基本内容是：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题

先写一下spfa算法

【初始化】

dis数组全部赋值为INF，pre数组全部赋值为-1（表示还不知道前驱），

dis[s] = 0 表示源点不要求最短路径（或者最短路径就是0）。

【队列+松弛操作】

读取队头顶点u，并将队头顶点u出队（记得消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新估计值（即令d[v]变小），那么就更新，另外，如果点v没有在队列中，那么要将点v入队（记得标记），如果已经在队列中了，那么就不用入队，这样不断从队列中取出顶点来进行松弛操作。

以此循环，直到队空为止就完成了单源最短路的求解。

【算法过程】

设立一个队列用来保存待优化的顶点，优化时每次取出队首顶点 u，并且用 u 点当前的最短路径估计值dis[u]对与 u 点邻接的顶点 v 进行松弛操作，如果 v 点的最短路径估计值dis[v]可以更小，且 v 点不在当前的队列中，就将 v 点放入队尾。这样不断从队列中取出顶点来进行松弛操作，直至队列空为止。

【检测负权回路】

方法：如果某个点进入队列的次数大于等于 n，则存在负权回路，其中 n 为图的顶点数。

说明：SPFA无法处理带负环的图。（X） 注意：：这个算法中的visited有一点点不一样是这个点出了队列以后把它标称未访问，之后还可以再把它加进来，在普通的bfs中就是第一个点变成visited加进队列，之后遍历上下左右，但凡满足要求的就加进队列，都附成visited 。这里要注意一下

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Stack; public class first { static int vertex_num; static int edge_num; static int source; static int []visited = new int[100]; static int []enqueue_num = new int[100]; //记录入队次数 static int dist[] = new int[100]; //源点到顶点i的最短距离 static int path[] = new int[100]; //记录最短路的路径 static int matrix[][] = new int[100][100]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); vertex_num = sc.nextInt(); //开始先输入顶点数，边数，源点 edge_num = sc.nextInt(); source = sc.nextInt(); for(int i = 0;i<vertex_num;i++){ for(int j = 0;j<vertex_num;j++){ matrix[i][j] =Integer.MAX_VALUE; } } for(int i = 1;i<edge_num;i++){ int u = sc.nextInt(); int v = sc.nextInt(); int w = sc.nextInt(); matrix[u][v] =w; } if(SPFA()){ Print(); }else{ System.out.println("这个图有负权环，不能用spfa"); } } static boolean SPFA(){ visited = new int[100]; enqueue_num = new int[100]; for(int i =0;i<vertex_num;i++){ dist[i] = Integer.MAX_VALUE; path[i] =source; } Queue<Integer> q = new LinkedList<Integer>(); ((LinkedList<Integer>) q).push(source); dist[source] = 0; visited[source] = 1; enqueue_num[source]++; while (!q.isEmpty()){ int u = q.poll(); visited[u] = 0; for(int v = 0;v<vertex_num;v++){ if(matrix[u][v] !=Integer.MAX_VALUE){ if(dist[u]+matrix[u][v]<dist[v]){ dist[v] = dist[u]+matrix[u][v]; path[v] = u; if(visited[v]==0){ ((LinkedList<Integer>) q).add(v); enqueue_num[v]++; if(enqueue_num[v]>=vertex_num){ return false; } visited[v] = 1; } } } } } return true; } static void Print(){ for(int i = 0;i<vertex_num;i++){ if(i!=source){ int p = i; Stack<Integer> s = new Stack<>(); System.out.print("顶点："+source+"到顶点:"+p+"的最短路径是:"); while (source!=p){ s.push(p); p = path[p]; } System.out.print(source); while (!s.isEmpty()){ System.out.print("--"+s.peek()); s.pop(); } System.out.println("最短路径是"+dist[i]); } } } }

写完spfa后就来写一下最大流最小费用吧 例题：https://www.luogu.org/problemnew/show/P3381#sub 参考：https://www.luogu.org/blog/21679/p3381-mu-ban-zui-xiao-fei-yong-zui-tai-liu

我的代码：（X）

import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner; public class fifth { static int n; static int m; static int s; static int t; static int flowd; static int costed; static int maxn = 5002; static int inf = Integer.MAX_VALUE; static List<edge> ed = new LinkedList<>(); static List<Integer> g[]= new LinkedList[maxn]; //g数组里每一个都是一个List public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); s = sc.nextInt(); t= sc.nextInt(); for(int i = 1;i<=m;i++){ int q1,q2,q3,q4; int u = -1; q1 = sc.nextInt(); q2 =sc.nextInt(); q3 = sc.nextInt(); q4= sc.nextInt(); ed.add(new edge(q1,q2,q3,0,q4)); g[q1].add(++u); ed.add(new edge(q2,q1,0,0,-q4)); g[q2].add(++u); } flowd = 0; costed = 0; while (bf()); System.out.println(flowd+" "+costed); } static boolean bf(){ for(int i = 1;i<=n;i++) d[i] = inf; Queue<Integer> h = new LinkedList(); ((LinkedList) h).add(s); while (!h.isEmpty()){ //bfs int x = h.poll(); inq[x] = false; for(int i = 0;i<g[x].size();i++){ edge e = ed.get(g[x].get(i)); if(e.cap>e.flow && d[e.to]>d[x]+e.cost){ d[e.to] = d[x]+e.cost; p[e.to] = g[x].get(i);//操作的是边的标号，可以把它放到edge用get取出 a[e.to] =Math.min(a[x],e.cap-e.flow); if(!inq[e.to]){ ((LinkedList<Integer>) h).add(e.to); inq[e.to] = true; } } } } if(d[t] ==inf) return false; flowd+= a[t]; costed+=a[t]*d[t]; int u = t; while (u!=s){ ed.get(p[u]).flow+=a[t]; ed.get(p[u]^1).flow-=a[t]; u = ed.get(p[u]).from; } return true; } static class edge{ int from,to,cap,flow,cost; public edge(int from, int to, int cap, int flow, int cost) { this.from = from; this.to = to; this.cap = cap; this.flow = flow; this.cost = cost; } } List<edge> list = new LinkedList<>(); static boolean inq[] = new boolean[maxn]; static int d[] = new int[maxn]; //到目前为止最小费用 static int p[]= new int[maxn];//记录上一条边（递归用） static int a[] = new int[maxn];//到当前为止的最大流量 }