GRL_6_B: Minimum Cost Flow

問題へのリンク

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("4 5 2");
            WillReturn.Add("0 1 2 1");
            WillReturn.Add("0 2 1 2");
            WillReturn.Add("1 2 1 1");
            WillReturn.Add("1 3 1 3");
            WillReturn.Add("2 3 2 1");
            //6
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mV;
    static int mGoalNode;
    static int mF;

    class EdgeInfoDef
    {
        internal int ToNode;
        internal int Capacity;
        internal int Cost;
        internal int Flow;
    }
    static Dictionary<long, List<EdgeInfoDef>> mEdgeInfoListDict = new Dictionary<long, List<EdgeInfoDef>>();

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

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

        SplitAct(InputList[0]);
        mV = wkArr[0];
        mGoalNode = mV - 1;
        mF = wkArr[2];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            int FromNode = wkArr[0];
            int ToNode = wkArr[1];
            int Capacity = wkArr[2];
            int Cost = wkArr[3];

            Action<int, int, int, int> AddEdgeAct = (pFromNode, pToNode, pCapacity, pCost) =>
            {
                if (mEdgeInfoListDict.ContainsKey(pFromNode) == false) {
                    mEdgeInfoListDict[pFromNode] = new List<EdgeInfoDef>();
                }
                var WillAdd = new EdgeInfoDef();
                WillAdd.ToNode = pToNode;
                WillAdd.Capacity = pCapacity;
                WillAdd.Cost = pCost;
                WillAdd.Flow = 0;
                mEdgeInfoListDict[pFromNode].Add(WillAdd);
            };

            AddEdgeAct(FromNode, ToNode, Capacity, Cost);
            AddEdgeAct(ToNode, FromNode, 0, -Cost);
        }

        // 逆辺と正辺で二重辺が存在しうるので、コストの昇順にソートしておく
        foreach (var EachPair in mEdgeInfoListDict) {
            EachPair.Value.Sort((pA, pB) => pA.Cost.CompareTo(pB.Cost));
        }

        while (mF > 0) {
            var NodeList = BellmanFord(0);
            if (NodeList == null) {
                Console.WriteLine(-1);
                return;
            }

            // 経路でのCapacityの最小値を求める
            var CapacityList = new List<int>();
            for (int I = 0; I <= NodeList.Count - 2; I++) {
                int FromNode = NodeList[I];
                int ToNode = NodeList[I + 1];

                foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoListDict[FromNode]) {
                    if (EachEdgeInfo.ToNode != ToNode) continue;
                    // 二重辺が存在しうるので、Capacityが0ならcontinue
                    if (EachEdgeInfo.Capacity == 0) continue;
                    CapacityList.Add(EachEdgeInfo.Capacity);
                    break;
                }
            }
            int CurrFlow = Math.Min(mF, CapacityList.Min());

            // フローを流して、逆辺を作る
            for (int I = 0; I <= NodeList.Count - 2; I++) {
                int FromNode = NodeList[I];
                int ToNode = NodeList[I + 1];

                // フローを流す
                foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoListDict[FromNode]) {
                    if (EachEdgeInfo.ToNode != ToNode) continue;
                    // 二重辺が存在しうるので、Capacityが0ならcontinue
                    if (EachEdgeInfo.Capacity == 0) continue;
                    EachEdgeInfo.Capacity -= CurrFlow;
                    EachEdgeInfo.Flow += CurrFlow;
                    break;
                }

                // 逆辺を作る
                foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoListDict[ToNode]) {
                    if (EachEdgeInfo.ToNode != FromNode) continue;
                    EachEdgeInfo.Capacity += CurrFlow;
                    break;
                }
            }
            mF -= CurrFlow;
        }

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

    // ベルマンフォードで、最小コストな経路を返す
    static List<int> BellmanFord(int pStaNode)
    {
        // どのノードから来たかのDict
        var PrevNodeDict = new Dictionary<int, int>();

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

        // 頂点数だけループ
        bool WillBreak = false;
        for (int I = 1; I <= mV; I++) {
            WillBreak = true;

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

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

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

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

        var NodeList = new List<int>();
        int CurrNode = mGoalNode;
        while (true) {
            NodeList.Add(CurrNode);
            if (CurrNode == pStaNode) break;
            CurrNode = PrevNodeDict[CurrNode];
        }
        NodeList.Reverse();
        return NodeList;
    }
}

解説

ベルマンフォードで最短経路を求め、
最短経路に、逆辺を作りつつ、流せるだけ流す。
のを繰り返してます。

逆辺によって、二重辺が発生することも考慮してます。