当前位置：首页 > news >正文

网络流算法

news 2025/5/19 8:46:15

参考：网络流算法详解-CSDN博客

网络流（二）最小费用最大流问题-CSDN博客

[网络流]学习笔记：一次理解网络流！-CSDN博客

最大流算法：

主要思想就是每次找到一条增广路径，直到网络中不存在增广路径时，就找到了最大流。

最大流算法证明（AI回答）：

最大流最小割定理证明

一、弱对偶性证明

对于任意可行流 ff 和任意割 (S,T)，其流量 ∣f∣ 不超过割的容量c(S,T)，即：

∣f∣≤∑u∈S,v∈Tc(u,v)

‌论证步骤‌：

‌流量分解‌：流的流量 ∣f∣ 可分解为割 (S,T) 中正向边流量之和减反向边流量之和，即：∣f∣=∑u∈S,v∈Tf(u,v)−∑u∈T,v∈Sf(u,v)
‌容量约束‌：由于 f(u,v)≤c(u,v) 且反向边流量 f(v,u)≥0，可得：∣f∣≤∑u∈S,v∈Tc(u,v)因此，最大流的值必然不超过最小割的容量

最大流算法证明

1. 最大流存在的必要条件

‌任意流的流量不超过任意割的容量‌：
对于割 (S,T)(，其容量 c(S,T)=∑u∈S,v∈Tc(u,v)，而流 f的流量满足 ∣f∣≤c(S,T)。

2. 算法终止时的流为最大流

‌构造割 (S,T)：当残留网络中无增广路径时，定义集合 S 包含从源点可达的所有节点，T=V∖S。
‌割的流量等于容量‌：此时 S 到 T 的所有边流量饱和，T 到 S 的边流量为零，因此 ∣f∣=c(S,T)∣。
‌最小割的存在性‌：由 ∣f∣≤c(S,T) 且构造的割容量等于当前流量，知当前流即为最大流

最小费用最大流算法

主要思想就是每次找到一条费用最小的增广路径，直到找不到网络中的增广路径时，就找到了最大流的最小费用。

最小费用最大流算法证明（AI回答）

1. 初始状态的正确性‌

‌零流的合法性‌：初始流 f=0，费用为0，显然满足费用最优性。

‌2. 归纳假设‌

假设当前流 f 是所有流量为 ∣f∣ 的可行流中费用最小的。需证明：通过增广一条费用最小的路径 P，得到流 f′，则 f′f′ 是所有流量为 ∣f∣+Δ的流中费用最小的。

‌3. 关键引理‌

‌引理‌：若每次增广的是残余网络中费用最小的路径，则新流的费用仍为当前流量下的最小值。

‌证明‌（反证法）：

‌假设存在更优流‌：假设存在另一流 f′′，满足 ∣f′′∣=∣f′∣ 且 cost(f′′)<cost(f′)。
‌流分解定理‌：将流 f′′−f 分解为若干简单路径和环的叠加。由于 cost(f′′−f)<cost(f′−f)，存在至少一条增广路径的费用比当前所选路径 P更低（否则总费用无法更小）。
‌矛盾‌：这与算法每次选择费用最小的路径增广矛盾，因此假设不成立。

‌4. 负权边的处理‌

‌反向边费用补偿‌：反向边费用为 −a(u,v)，确保增广路径费用计算的正确性。例如，若从 u→v原有流量 f(u,v)，则反向边 v→u允许回退流量，并补偿费用。
‌SPFA算法的必要性‌：由于反向边可能引入负权边，需使用SPFA算法寻找最短路（Dijkstra需结合势函数才可处理负权）。

‌5. 终止条件‌

当残余网络中不存在源点到汇点的增广路径时，当前流为最大流。根据归纳法，此时的费用也为最小值

‌复杂度分析‌

‌时间复杂度‌：依赖于增广次数和最短路径算法复杂度。若采用SPFA，复杂度为 O(F⋅VE)（F 为最大流量，E 和 V 为边数和顶点数）。
‌势函数优化‌：通过势函数将边权调整为非负，可使用Dijkstra算法减少时间复杂度至 O(F⋅(E+Vlog⁡V))

总结：

最大流算法和最小费用算法都有贪心的思想，每次迭代都会离最大流网络更近一步。网络流的题目难度主要在抽象建模，很多问题同网络流联系起来并不那边直观。

最小费用最大流算法代码实现：

因为引入了反向边，每次找增广路时需要更新正向边和反向边的流量，就需要快查找到增广路径上的边。所以在网络流算法中一般用链式前向星这种数据结构存储图比较高效方便。需要注意反向边的容量为0，花费为负。

题目：863F - Almost Permutation

https://codeforces.com/contest/863/problem/F

该题的关键在于构造图，构造1个节点（下标0）代表原点S，n个节点（下标1到n）代表从1到n的n个值，n个节点（下标n+1到2n）代表从1到n的n个位置，1个终点T。其中原点到每个下标1到n的点都连50条边，费用为2*j-1，（j表示第j条边），下标1到n的点根据题目条件限制分别连上多条边到下标n+1到2*n的点，每个下标n+1到2*n的点在连一条边到终点，其中流量都为1。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;public class Main {public static void main(String args[]) {new Main().run();}FastReader in = new FastReader();PrintWriter out = new PrintWriter(System.out);void run() {work();out.flush();}long mod=998244353;long inf=Long.MAX_VALUE/3;long gcd(long a,long b) {return a==0?b:gcd(b%a,a);}Edge[] edges;int[] head;int[] route;int maxn=120;int S,T;int cur;void addEdge(int s,int e,int flow,int cap,int cost){Edge edge=new Edge(s,e,flow,cap,cost,head[s]);edges[cur]=edge;head[s]=cur;cur++;}void work(){int n=ni();edges=new Edge[maxn*100];head=new int[maxn];Arrays.fill(head,-1);route=new int[maxn];boolean[][] rec=new boolean[n+1][n+1];for(int q=ni();q>0;q--){int t=ni(),l=ni(),r=ni(),v=ni();if(t==1){for(int i=l;i<=r;i++){for(int j=1;j<v;j++)rec[i][j]=true;}}else{for(int i=l;i<=r;i++){for(int j=v+1;j<=n;j++)rec[i][j]=true;}}}//S=0,T=110S=0;T=110;//添加值1——nfor(int i=1;i<=n;i++){for(int j=0;j<n;j++){addEdge(S,i,0,1,2*j+1);addEdge(i,S,0,0,-(2*j+1));}}//位置n+1——2*nfor(int i=1;i<=n;i++){boolean f=false;for(int j=1;j<=n;j++){if(!rec[i][j]){f=true;addEdge(j,i+n,0,1,0);addEdge(i+n,j,0,0,0);}}if(!f){out.println(-1);return;}}for(int i=1;i<=n;i++){addEdge(i+n,T,0,1,0);addEdge(T,i+n,0,0,0);}out.println(mcmf());}//最小费用最大流Minimum Cost Maximum Flowint mcmf(){int sumCost=0;int maxFlow=0;while(spfa()){int v=999999999;//查找最小流量for(int i=route[T];i!=-1;i=route[edges[i].from]){v=Math.min(v,edges[i].cap-edges[i].flow);}//更新流量for(int i=route[T];i!=-1;i=route[edges[i].from]){
//                c+=edges[i].cost;edges[i].flow+=v;edges[i^1].flow-=v;//注意：i是奇数或偶数时不同}}for(int i=0;i<edges.length&&edges[i]!=null;i+=2){Edge edge=edges[i];sumCost+=edge.flow*edge.cost;//最大流==某一个割中的S部分的点流向T部分点的流-T部分的点流向S部分点的流//这里已T点的边为割，T部分的点流向S部分点的流为0if(edge.to==T){maxFlow+=edge.flow;}}return sumCost;}//用于求含负权边的单源最短路径boolean spfa(){LinkedList<Integer> queue=new LinkedList<>();queue.add(S);boolean[] vis=new boolean[maxn];int[] rec=new int[maxn];Arrays.fill(rec,999999999);Arrays.fill(route,-1);rec[S]=0;while(queue.size()>0){Integer node = queue.poll();vis[node]=false;for(int i=head[node];i!=-1;i=edges[i].next){Edge edge = edges[i];if(rec[edge.to]>rec[node]+edge.cost&&edge.flow<edge.cap){rec[edge.to]=rec[node]+edge.cost;route[edge.to]=i;if(!vis[edge.to]){queue.add(edge.to);vis[edge.to]=true;}}}}if(rec[T]==999999999){return false;}return true;}class Edge{int from,to,flow,cap,cost,next;Edge(int from,int to,int flow,int cap,int cost,int next){this.from=from;this.to=to;this.flow=flow;this.cap=cap;this.cost=cost;this.next=next;}}@SuppressWarnings("unused")private ArrayList<Integer>[] ng(int n, int m) {ArrayList<Integer>[] graph=(ArrayList<Integer>[])new ArrayList[n];for(int i=0;i<n;i++) {graph[i]=new ArrayList<>();}for(int i=1;i<=m;i++) {int s=in.nextInt()-1,e=in.nextInt()-1;graph[s].add(e);graph[e].add(s);}return graph;}private ArrayList<long[]>[] ngw(int n, int m) {ArrayList<long[]>[] graph=(ArrayList<long[]>[])new ArrayList[n];for(int i=0;i<n;i++) {graph[i]=new ArrayList<>();}for(int i=1;i<=m;i++) {long s=in.nextLong()-1,e=in.nextLong()-1,w=in.nextLong();graph[(int)s].add(new long[] {e,w});graph[(int)e].add(new long[] {s,w});}return graph;}private int ni() {return in.nextInt();}private long nl() {return in.nextLong();}private double nd() {return in.nextDouble();}private String ns() {return in.next();}private long[] na(int n) {long[] A=new long[n];for(int i=0;i<n;i++) {A[i]=in.nextLong();}return A;}private int[] nia(int n) {int[] A=new int[n];for(int i=0;i<n;i++) {A[i]=in.nextInt();}return A;}
}class FastReader
{BufferedReader br;StringTokenizer st;InputStreamReader input;//no bufferpublic FastReader(){br=new BufferedReader(new InputStreamReader(System.in));}public FastReader(boolean isBuffer){if(!isBuffer){input=new InputStreamReader(System.in);}else{br=new BufferedReader(new InputStreamReader(System.in));}}public boolean hasNext(){try{String s=br.readLine();if(s==null){return  false;}st=new StringTokenizer(s);}catch(IOException e){e.printStackTrace();}return true;}public String next(){if(input!=null){try {StringBuilder sb=new StringBuilder();int ch=input.read();while(ch=='\n'||ch=='\r'||ch==32){ch=input.read();}while(ch!='\n'&&ch!='\r'&&ch!=32){sb.append((char)ch);ch=input.read();}return sb.toString();}catch (Exception e){e.printStackTrace();}}while(st==null || !st.hasMoreElements())//回车，空行情况{try {st = new StringTokenizer(br.readLine());} catch (IOException e) {e.printStackTrace();}}return st.nextToken();}public int nextInt(){return (int)nextLong();}public long nextLong() {try {if(input!=null){long ret=0;int b=input.read();while(b<'0'||b>'9'){b=input.read();}while(b>='0'&&b<='9'){ret=ret*10+(b-'0');b=input.read();}return ret;}}catch (Exception e){e.printStackTrace();}return Long.parseLong(next());}public double nextDouble(){return Double.parseDouble(next());}
}

查看全文

http://www.xdnf.cn/news/518257.html