典型問題(上級) F 最小費用流

問題へのリンク

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("6 9 3");
            WillReturn.Add("1 2 3 2");
            WillReturn.Add("1 3 2 1");
            WillReturn.Add("2 3 2 2");
            WillReturn.Add("2 4 3 4");
            WillReturn.Add("3 4 5 1");
            WillReturn.Add("3 5 6 2");
            WillReturn.Add("4 5 2 2");
            WillReturn.Add("4 6 6 3");
            WillReturn.Add("5 6 10 2");
            //18
        }
        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(pX => long.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        long SinkNode = wkArr[0];
        long F = wkArr[2];

        var InsMinCostFlow = new MinCostFlow(F, 1, SinkNode);
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long FromNode = wkArr[0];
            long ToNode = wkArr[1];
            long Capacity = wkArr[2];
            long Cost = wkArr[3];

            InsMinCostFlow.AddEdge(FromNode, ToNode, Capacity, Cost);
        }
        bool Result;
        long MinCostFlow;
        InsMinCostFlow.DeriveMinCostFlow(out Result, out MinCostFlow);
        Console.WriteLine(MinCostFlow);
    }
}

// 最小費用流のSolverクラス
#region MinCostFlow
internal class MinCostFlow
{
    private long mFlow;
    private long mSourceNode;
    private long mSinkNode;

    private long mNextEdgeID = 0;

    private HashSet<long> mNodeSet = new HashSet<long>();

    // 枝情報
    private class EdgeInfoDef
    {
        internal long EdgeID;
        internal long FromNode;
        internal long ToNode;
        internal long Capacity;
        internal long Cost;
        internal long Flow;
        internal EdgeInfoDef RevPointer; // 逆辺へのポインタ
    }
    private Dictionary<long, List<EdgeInfoDef>> mEdgeInfoListDict =
        new Dictionary<long, List<EdgeInfoDef>>();

    // 枝[枝ID]なDict
    private Dictionary<long, EdgeInfoDef> mEdgeDict = new Dictionary<long, EdgeInfoDef>();

    // コンストラクタ
    internal MinCostFlow(long pFlow, long pSourceNode, long pSinkNode)
    {
        mFlow = pFlow;
        mSourceNode = pSourceNode;
        mSinkNode = pSinkNode;
    }

    // グラフに辺を追加(逆辺はメソッド内部で自動追加)
    internal void AddEdge(long pFromNode, long pToNode, long pCapacity, long pCost)
    {
        mNodeSet.Add(pFromNode);
        mNodeSet.Add(pToNode);

        if (mEdgeInfoListDict.ContainsKey(pFromNode) == false) {
            mEdgeInfoListDict[pFromNode] = new List<EdgeInfoDef>();
        }
        if (mEdgeInfoListDict.ContainsKey(pToNode) == false) {
            mEdgeInfoListDict[pToNode] = new List<EdgeInfoDef>();
        }

        var WillAddSei = new EdgeInfoDef();
        WillAddSei.EdgeID = mNextEdgeID++;
        WillAddSei.FromNode = pFromNode;
        WillAddSei.ToNode = pToNode;
        WillAddSei.Capacity = pCapacity;
        WillAddSei.Cost = pCost;
        WillAddSei.Flow = 0;
        mEdgeDict[WillAddSei.EdgeID] = WillAddSei;

        var WillAddRev = new EdgeInfoDef();
        WillAddRev.EdgeID = mNextEdgeID++;
        WillAddRev.FromNode = pToNode;
        WillAddRev.ToNode = pFromNode;
        WillAddRev.Capacity = 0;
        WillAddRev.Cost = -pCost;
        WillAddRev.Flow = 0;
        WillAddRev.RevPointer = WillAddSei;
        mEdgeDict[WillAddRev.EdgeID] = WillAddRev;

        WillAddSei.RevPointer = WillAddRev;

        mEdgeInfoListDict[pFromNode].Add(WillAddSei);
        mEdgeInfoListDict[pToNode].Add(WillAddRev);
    }

    // 最小費用流を計算して返す
    internal void DeriveMinCostFlow(out bool pHasAnswer, out long pMinCostFlow)
    {
        pHasAnswer = false;
        pMinCostFlow = 0;
        while (mFlow > 0) {
            var EdgeIDList = ExecBellmanFord();
            if (EdgeIDList == null) {
                return; // 解なしの場合
            }

            // 経路でのCapacityの最小値を求める
            var CapacityList = new List<long>();
            foreach (long EachEdgeID in EdgeIDList) {
                EdgeInfoDef CurrEdge = mEdgeDict[EachEdgeID];
                CapacityList.Add(CurrEdge.Capacity);
            }
            long CurrFlow = Math.Min(mFlow, CapacityList.Min());

            // フローを流して、逆辺を作る
            foreach (long EachEdgeID in EdgeIDList) {
                EdgeInfoDef CurrEdge = mEdgeDict[EachEdgeID];
                CurrEdge.Capacity -= CurrFlow;
                CurrEdge.Flow += CurrFlow;

                EdgeInfoDef RevEdge = mEdgeDict[EachEdgeID].RevPointer;
                RevEdge.Capacity += CurrFlow;
            }
            mFlow -= CurrFlow;
        }

        // コストを計算する
        long Answer = 0;
        foreach (List<EdgeInfoDef> EachEdgeList in mEdgeInfoListDict.Values) {
            foreach (EdgeInfoDef EachEdgeInfo in EachEdgeList) {
                Answer += EachEdgeInfo.Flow * EachEdgeInfo.Cost;
            }
        }
        pHasAnswer = true;
        pMinCostFlow = Answer;
    }

    // ベルマンフォードで、最小コストな経路を返す
    private List<long> ExecBellmanFord()
    {
        // 遷移してきた枝ID[ノード]なDict
        var PrevEdgeDict = new Dictionary<long, long>();

        // 各ノードまでの距離のDict
        var SumCostDict = new Dictionary<long, long>();
        SumCostDict[mSourceNode] = 0;

        // 頂点数だけループ
        long NodeCnt = mNodeSet.Count;
        bool WillBreak = false;
        for (long I = 1; I <= NodeCnt; I++) {
            WillBreak = true;

            foreach (long EachKey in SumCostDict.Keys.ToArray()) {
                if (mEdgeInfoListDict.ContainsKey(EachKey) == false)
                    continue;

                // そのノードから訪問可能なノードで
                // 最短距離を更新可能なら更新
                foreach (EdgeInfoDef EachNodeInfo in mEdgeInfoListDict[EachKey]) {
                    if (EachNodeInfo.Capacity == 0) continue;

                    long wkSumCost = SumCostDict[EachKey] + EachNodeInfo.Cost;
                    if (SumCostDict.ContainsKey(EachNodeInfo.ToNode)) {
                        if (SumCostDict[EachNodeInfo.ToNode] <= wkSumCost) {
                            continue;
                        }
                    }
                    SumCostDict[EachNodeInfo.ToNode] = wkSumCost;
                    PrevEdgeDict[EachNodeInfo.ToNode] = EachNodeInfo.EdgeID;
                    WillBreak = false;
                }
            }
            if (WillBreak) break;
        }

        if (SumCostDict.ContainsKey(mSinkNode) == false) {
            return null;
        }

        var EdgeIDList = new List<long>();
        long CurrNode = mSinkNode;
        while (true) {
            long EdgeID = PrevEdgeDict[CurrNode];
            EdgeIDList.Add(EdgeID);
            CurrNode = mEdgeDict[EdgeID].FromNode;

            if (CurrNode == mSourceNode) break;
        }
        EdgeIDList.Reverse();
        return EdgeIDList;
    }
}
#endregion

解説

最小費用流のSolverクラスを使ってます。