典型問題(上級) E 最大流

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5 7");
            WillReturn.Add("1 2 8");
            WillReturn.Add("1 3 10");
            WillReturn.Add("2 4 5");
            WillReturn.Add("2 5 5");
            WillReturn.Add("3 2 9");
            WillReturn.Add("3 4 6");
            WillReturn.Add("4 5 12");
            //16
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => long.Parse(X)).ToArray();

        SplitAct(InputList[0]);
        long V = wkArr[0];

        var InsDinic = new Dinic();

        // グラフに枝を追加
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long FromNode = wkArr[0];
            long ToNode = wkArr[1];
            long Capacity = wkArr[2];
            InsDinic.add_edge(FromNode, ToNode, Capacity);
        }

        long Answer = InsDinic.max_flow(1, V);
        Console.WriteLine(Answer);
    }
}

// Dinic法
#region Dinic
internal class Dinic
{
    const long MAX_V = 600000 + 100;

    // 辺を表すクラス
    private class edge
    {
        internal long to;  // 行き先
        internal long cap; // 容量
        internal long rev; // 逆辺
    }

    private List<edge>[] G = new List<edge>[MAX_V]; // グラフの隣接リスト表現
    private long[] level = new long[MAX_V];         // sからの距離
    private long[] iter = new long[MAX_V];          // どこまで調べ終わったか

    // fromからtoへ向かう容量capの辺をグラフに追加する
    internal void add_edge(long from, long to, long cap)
    {
        if (G[from] == null) G[from] = new List<edge>();
        if (G[to] == null) G[to] = new List<edge>();

        var edge1 = new edge();
        edge1.to = to;
        edge1.cap = cap;
        edge1.rev = G[to].Count;
        G[from].Add(edge1);

        var edge2 = new edge();
        edge2.to = from;
        edge2.cap = 0;
        edge2.rev = G[from].Count - 1;
        G[to].Add(edge2);
    }

    // sからの最短距離をBFSで計算する
    private void bfs(long s)
    {
        for (long i = 0; i <= level.GetUpperBound(0); i++) {
            level[i] = -1;
        }
        var que = new Queue<long>();
        level[s] = 0;
        que.Enqueue(s);
        while (que.Count > 0) {
            long v = que.Dequeue();
            for (long i = 0; i < G[v].Count; i++) {
                edge e = G[v][(int)i];
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    que.Enqueue(e.to);
                }
            }
        }
    }

    // 増加パスをDFSで探す
    private long dfs(long v, long t, long f)
    {
        if (v == t) return f;
        for (; iter[v] < G[v].Count; iter[v]++) {
            edge e = G[v][(int)iter[v]];
            if (e.cap > 0 && level[v] < level[e.to]) {
                long d = dfs(e.to, t, Math.Min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][(int)e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    // sからtへの最大流を求める
    internal long max_flow(long s, long t)
    {
        long flow = 0;
        for (; ; ) {
            bfs(s);
            if (level[t] < 0) return flow;
            Array.Clear(iter, 0, iter.Length);
            long f;
            while ((f = dfs(s, t, long.MaxValue)) > 0) {
                flow += f;
            }
        }
    }
}
#endregion

解説

Dinic法で解いてます。