第7回PAST M 分割

問題へのリンク

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 10");
            WillReturn.Add("4 25 1000000000 9 19 22");
            //44
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 100");
            WillReturn.Add("3 1 4 1 5");
            //112
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 5301");
            WillReturn.Add("6708 1391 3108 7953 7797 2370 7699 1098 2362 2359");
            //17095
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long C = wkArr[1];

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        var NodeNameList = new List<string>();

        NodeNameList.Add("Source");
        NodeNameList.Add("Term");
        NodeNameList.Add("Sink");
        for (long I = 0; I <= AArr.GetUpperBound(0); I++) {
            NodeNameList.Add("X" + I.ToString());
            if (I > 0) {
                NodeNameList.Add("Y" + I.ToString());
            }
        }

        // ノードID[ノード名]なDict
        var NodeIDDict = new Dictionary<string, long>();
        foreach (string EachStr in NodeNameList) {
            NodeIDDict[EachStr] = NodeIDDict.Count;
        }

        var InsMinCostFlow = new MinCostFlow(AArr.Length, NodeIDDict["Source"], NodeIDDict["Sink"]);

        for (long I = 0; I <= AArr.GetUpperBound(0); I++) {
            long FromNode = NodeIDDict["Source"];
            long ToNode = NodeIDDict["X" + I.ToString()];
            InsMinCostFlow.AddEdge(FromNode, ToNode, 1, 0);
        }

        for (long I = 0; I <= AArr.GetUpperBound(0); I++) {
            long FromNode = NodeIDDict["X" + I.ToString()];
            for (long J = I + 1; J <= AArr.GetUpperBound(0); J++) {
                long ToNode = NodeIDDict["Y" + J.ToString()];

                long Cost = Math.Abs(AArr[I] - AArr[J]);
                InsMinCostFlow.AddEdge(FromNode, ToNode, 1, Cost);
            }
        }

        for (long I = 0; I <= AArr.GetUpperBound(0); I++) {
            long FromNode = NodeIDDict["X" + I.ToString()];
            long ToNode = NodeIDDict["Term"];
            InsMinCostFlow.AddEdge(FromNode, ToNode, 1, C);
        }

        for (long J = 1; J <= AArr.GetUpperBound(0); J++) {
            long FromNode = NodeIDDict["Y" + J.ToString()];
            long ToNode = NodeIDDict["Sink"];
            InsMinCostFlow.AddEdge(FromNode, ToNode, 1, 0);
        }
        InsMinCostFlow.AddEdge(NodeIDDict["Term"], NodeIDDict["Sink"], AArr.Length, 0);

        bool Result; long Answer;
        InsMinCostFlow.DeriveMinCostFlow(out Result, out Answer);
        Console.WriteLine(Answer);
    }
}

// 最小費用流の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

解説

要素を全探索し、
各要素の次にあるのは、別要素か、終端(ターミネート)
であると考えれば、最小費用流で解けます。