# 算法笔记_132:最大流量有关问题（Java）

www.MyException.Cn  网友分享于：2013-04-21  浏览：0次

1 问题描述

2 解决方案

# 2 解决方案

（1）残留网络

（2）增广路径

（3）流网络的割

```package com.liuzhen.practice;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
public static int maxV = Integer.MAX_VALUE;
public static int[][] capacity = new int[6][6]; //用于统计给定图前向边和后向边剩余流量
public static int[] flow = new int[6];  //用于统计从源点到图中任意一点i的最大可增加的流量
public static int[] pre = new int[6];  //用于记录当前到达顶点的前驱顶点

public int bfs(int[][] graph) {  //使用BFS遍历，寻找给定图的增广路径
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i = 0;i < 6;i++) {
pre[i] = -1;   //初始化所有顶点的前驱顶点为-1
}
pre[0] = 0;     //源点的前驱顶点设定为自己
flow[0] = maxV; //源点的前驱顶点到源点的增加流量设定为无穷大
while(!list.isEmpty()) {
int index = list.get(0);
list.remove(0);
if(index == 5)
break;
for(int i = 0;i < graph.length;i++) {
if(capacity[index][i] > 0 && pre[i] == -1) {//当顶点i未被访问且到达顶点i有剩余流量时
pre[i] = index;  //顶点i的前驱顶点为index
flow[i] = Math.min(flow[index], capacity[index][i]);
}
}
}
if(pre[5] != -1)
return flow[5];
return -1;
}

public void getResult(int[][] graph) {
int result = 0;
int temp = bfs(graph);
while(temp != -1) {
result = result + temp;
int start = pre[5];
int end = 5;
while(start != 0) {
capacity[start][end] -= temp;   //前向边剩余流量减少temp
capacity[end][start] += temp;   //后向边剩余流量增加temp
end = start;
start = pre[end];
}
capacity[0][end] -= temp;
capacity[end][0] += temp;
temp = bfs(graph);
}
System.out.println("给定图的最大流量为："+result);
return;
}

public static void main(String[] args) {
Main test = new Main();
int[][] graph = new int[6][6];
Scanner in = new Scanner(System.in);
int num = in.nextInt();   // 给定图的边数目
for(int i = 0;i < num;i++) {
int a = in.nextInt();
int b = in.nextInt();
int value = in.nextInt();
graph[a - 1][b - 1] = value;
capacity[a - 1][b - 1] = value;//前向边起始剩余流量为边的容量，后向边起始剩余流量为0
}
test.getResult(graph);
}
}```

```7
1 2 2
1 3 4
2 5 3
2 3 5
4 3 1
5 6 4
3 2 6

3.《算法设计与分析基础》第3版   Anany Levitin 著   潘彦 译