网络流算法之最大流量计算

大家好，我是快到各种996福报厂被优化年龄的中年人老正经兔，继续马克一下。。。

网络流是本宝宝的盲点，网络流中最常见最主要的问题是求最大流。以前刷题没有碰到过，所以前面不会。

现有一问题如下：

Implement the Ford-Fulkerson method for finding maximum flow in graphs with only integer edge ca­pacities, in either C, C++, C#, Java, or Python. Be efficient and implement it in <O(mC) time, where m is the number of edges in the graph and C is the maximum capacity of any edge in the graph. We suggest using BFS or DFS to find augmenting paths. 

The input will start with a positive integer, giving the number of instances that follow. For each instance, there will be two positive integers, indicating the number of nodes n = |V| in the graph and the number of edges |E| in the graph. Following this, there will be additional lines describing the edges. Each edge line consists of a number indicating the source node, a number indicating the destination node, and a capacity. The nodes are not listed separately, but are numbered {1... n].

Your program should compute the maximum flow value from node 1 to node n in each given graph.

A sample input is the following:

即：有一有向图，有1、2、3...N总共N个点，求1到N的最大流量。

众所周知，计算最大流主要有Ford Fulkerson和Edmonds Karp两种基础算法，而Edmonds Karp其实是Ford Fulkerson在找增广路径的时候用BFS实现的变形。

得到一个课件准备好好学习如何实现，然而：

这tmd谁看得懂？？？（现在因为会了所以回过头来看懂了，前面不懂的时候完全看晕）

还好，找到了知乎上的一篇笔记，看懂了原理。

https://zhuanlan.zhihu.com/p/122375531

首先又是现学的java的实现，写java实在是太麻烦了……

import java.util.Scanner;
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;

class main {
    public static int FordFulkerson(int[][] graph,int s,int t) {
        int max_flow=0;
        int flow,tmp;
        int[] parent=new int[t+1];
        for (int k=0;k<=t;k++) {parent[k]=-1;}
        while (bfs(graph,s,t,parent)==1){
            flow=0x7fffffff;
            tmp=t;
            while (tmp!=s){
                flow=Math.min(flow,graph[parent[tmp]][tmp]);
                tmp=parent[tmp];
            }
            max_flow+=flow;
            tmp=t;
            while (tmp!=s){
                graph[parent[tmp]][tmp]-=flow;
                graph[tmp][parent[tmp]]+=flow;
                tmp=parent[tmp];
            }
        }
        return max_flow;
    }

    public static int bfs(int[][] graph,int s,int t,int[] parent){
        Queue<Integer> queue= new LinkedList<>();
        queue.offer(s);
        int[] visited=new int[t+1];
        visited[s]=1;
        for (int i=0;i<=t;i++){
            visited[i]=-1;
        }
        while (!queue.isEmpty()){
            int p=queue.poll();
            if (p==t){return 1;}
            for (int j=1;j<=t;j++){
                if (visited[j]==-1 && graph[p][j]!=0){
                    queue.offer(j);
                    parent[j]=p;
                    visited[j]=1;
                }
            }
        }
        return 0;
    }

    public static int[][] readData(int t,int n,Scanner scanner){
        int[][] graph=new int[t+1][t+1];
        for (int j=0; j<=t; j++) {
            for (int i=0; i<=t; i++) {
                graph[i][j]=0;
            }
        }
        for (int j=1; j<=n; j++) {
            int u=scanner.nextInt();
            int v=scanner.nextInt();
            int c=scanner.nextInt();
            graph[u][v]+=c;
        }
        return graph;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int[] res=new int[num];
        for (int i=0; i<num; i++) {
            int t = scanner.nextInt();
            int n= scanner.nextInt();
            int[][] graph=readData(t,n,scanner);
            int max_flow=FordFulkerson(graph,1,t);
            res[i]=max_flow;
        }
        scanner.close();
        for (int k=0;k<num;k++) {
            System.out.println(res[k]);
        }
    }
}

然后是python，实际是先写的python，后改的java。。。

from collections import defaultdict

def readData(n):
    items=defaultdict(int)
    for i in range(n):
        x,y,z=[int(x) for x in input().split()]
        items[(x,y)]+=z
    return items

def bfs(graph,s,t,parent):
    visited={s}
    li=[s]
    while li!=[]:
        p=li.pop(0)
        if p==t:return True
        for x in range(1,t+1):
            if (p,x) in graph and graph[(p,x)]>0 and x not in visited:
                visited.add(x)
                li.append(x)
                parent[x]=p
    return False

def FordFulkerson(graph,s,t):
    maxflow=0
    parent = defaultdict(int)
    while bfs(graph, s, t, parent):
        flow = float("Inf")
        tmp = t
        while tmp != s:
            flow = min(flow, graph[(parent[tmp],tmp)])
            tmp = parent[tmp]
        maxflow += flow
        v = t
        while v != s:
            u = parent[v]
            graph[(u,v)] -= flow
            graph[(v,u)] += flow
            v = parent[v]
    return maxflow

if __name__ == '__main__':
    num = int(input())
    res=[]
    for i in range(num):
        t, n = [int(x) for x in input().split()]
        graph=readData(n)
        maxflow=FordFulkerson(graph,1,t)
        res.append(maxflow)
    for x in res:
        print (x)

真是好困难。

几年前和一个当时保送了北大的同学聊天中，我们都对竟然没有人引导我们参加信竞感到可惜。

只不过现在又觉得，以我在这方面的天赋，就算当时参加了，估计也只能拿个省二，最多就是个没保送资格的省一。可能最终还是只能去勃二本。

不过又想了下，哪怕是竞赛菜鸡，后面的什么力扣难题、什么湾区公司面试应该也小case，应该会随大流去美帝念硕，这会儿肯定在美帝当码农拿着百万年薪了……