第3回PAST O 輪投げ

問題へのリンク

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("2 1");
            WillReturn.Add("3 2");
            WillReturn.Add("3 3");
            WillReturn.Add("100000 100000 100000");
            //81
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 2");
            WillReturn.Add("2 4 3 3");
            WillReturn.Add("4 2 3 3");
            WillReturn.Add("100000 100000 100000");
            //210
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("20 19");
            WillReturn.Add("3 2 3 4 3 3 2 3 2 2 3 3 4 3 2 4 4 3 3 4");
            WillReturn.Add("2 3 4 2 4 3 3 2 4 2 4 3 3 2 3 4 4 4 2 2");
            WillReturn.Add("3 4 5");
            //-1417
        }
        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 N = wkArr[0];
        long M = wkArr[1];

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

        SplitAct(InputList.Last());
        long R1 = wkArr[0];
        long R2 = wkArr[1];
        long R3 = wkArr[2];

        var NodeNameList = new List<string>();

        NodeNameList.Add("Source");

        NodeNameList.Add("R1");
        NodeNameList.Add("R2");
        NodeNameList.Add("R3");

        for (long I = 1; I <= N; I++) {
            NodeNameList.Add("棒" + I.ToString());
        }

        NodeNameList.Add("Sink");

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

        var InsMinCostFlow = new MinCostFlow(M * 3, NodeIDDict["Source"], NodeIDDict["Sink"]);
        InsMinCostFlow.AddEdge(NodeIDDict["Source"], NodeIDDict["R1"], M, 0);
        InsMinCostFlow.AddEdge(NodeIDDict["Source"], NodeIDDict["R2"], M, 0);
        InsMinCostFlow.AddEdge(NodeIDDict["Source"], NodeIDDict["R3"], M, 0);

        for (long I = 1; I <= 3; I++) {
            long FromNode = NodeIDDict["R" + I.ToString()];
            for (long J = 1; J <= N; J++) {
                long ToNode = NodeIDDict["棒" + J.ToString()];

                long Syokou = AArr[J - 1];
                long Kouhi = BArr[J - 1];

                long Cost = Syokou /** Kouhi*/;
                for (long K = 1; K <= I; K++) {
                    Cost *= Kouhi;
                }
                long Hou = R1;
                if (I == 2) Hou = R2;
                if (I == 3) Hou = R3;

                InsMinCostFlow.AddEdge(FromNode, ToNode, 1, -1 * (Cost % Hou));
            }
        }

        for (long I = 1; I <= N; I++) {
            long FromNode = NodeIDDict["棒" + I.ToString()];

            long Syokou = AArr[I - 1];
            long Kouhi = BArr[I - 1];

            long Cost = Syokou;
            var CostList = new List<long>();
            for (long J = 1; J <= 3; J++) {
                Cost *= Kouhi;
                CostList.Add(Cost);
            }

            for (int J = 0; J <= CostList.Count - 1; J++) {
                long CurrCost = CostList[0];
                if (J == 1) {
                    CurrCost = CostList[1] - CostList[0];
                }
                if (J == 2) {
                    CurrCost = CostList[2] - CostList[1];
                }
                InsMinCostFlow.AddEdge(FromNode, NodeIDDict["Sink"], 1, CurrCost);
            }
        }

        bool Result; long Answer;
        InsMinCostFlow.DeriveMinCostFlow(out Result, out Answer);
        Console.WriteLine(-1 * 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の最小値を求める
            //Console.WriteLine("フローを流します");
            var CapacityList = new List<long>();
            foreach (long EachEdgeID in EdgeIDList) {
                EdgeInfoDef CurrEdge = mEdgeDict[EachEdgeID];
                CapacityList.Add(CurrEdge.Capacity);

                //Console.WriteLine("FromNode={0},ToNode={1},Capacity={2},Cost={3}",
                //    CurrEdge.FromNode, CurrEdge.ToNode, CurrEdge.Capacity, CurrEdge.Cost);
            }
            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

解説

最小費用流問題に帰着させてます。