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>();

        list.add(0);      //源点为顶点0

        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]);

                    list.add(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