第8回PAST K ニワトリのお見合い

問題へのリンク

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 4");
            WillReturn.Add("0010");
            WillReturn.Add("1111");
            WillReturn.Add("0010");
            WillReturn.Add("0010");
            WillReturn.Add("7 4");
            WillReturn.Add("6 1");
            WillReturn.Add("4 9");
            WillReturn.Add("5 3");
            WillReturn.Add("1 1");
            WillReturn.Add("2 8");
            WillReturn.Add("9 4");
            WillReturn.Add("6 5");
            //49
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 4");
            WillReturn.Add("0000");
            WillReturn.Add("0000");
            WillReturn.Add("0000");
            WillReturn.Add("1 2");
            WillReturn.Add("3 4");
            WillReturn.Add("5 6");
            WillReturn.Add("7 8");
            WillReturn.Add("9 10");
            WillReturn.Add("11 12");
            WillReturn.Add("13 14");
            //56
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 3");
            WillReturn.Add("100");
            WillReturn.Add("100");
            WillReturn.Add("100");
            WillReturn.Add("111");
            WillReturn.Add("5 4");
            WillReturn.Add("3 2");
            WillReturn.Add("9 8");
            WillReturn.Add("100 1");
            WillReturn.Add("200 50");
            WillReturn.Add("10 9");
            WillReturn.Add("8 6");
            //332
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ABInfoDef
    {
        internal long A;
        internal long B;
    }
    static List<ABInfoDef> mABInfoList = new List<ABInfoDef>();

    struct CDInfoDef
    {
        internal long C;
        internal long D;
    }
    static List<CDInfoDef> mCDInfoList = new List<CDInfoDef>();

    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 P = wkArr[0];
        long Q = wkArr[1];

        char[,] BanArr = CreateBanArr(InputList.Skip(1).Take((int)P));

        foreach (string EachStr in InputList.Skip(1 + (int)P).Take((int)P)) {
            SplitAct(EachStr);
            ABInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            mABInfoList.Add(WillAdd);
        }

        foreach (string EachStr in InputList.Skip(1 + (int)P + (int)P)) {
            SplitAct(EachStr);
            CDInfoDef WillAdd;
            WillAdd.C = wkArr[0];
            WillAdd.D = wkArr[1];
            mCDInfoList.Add(WillAdd);
        }

        var NodeNameList = new List<string>();
        NodeNameList.Add("Source");
        for (long I = 1; I <= P; I++) {
            NodeNameList.Add("オス" + I.ToString());
        }
        for (long I = 1; I <= Q; 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(P, NodeIDDict["Source"], NodeIDDict["Sink"]);
        for (long I = 1; I <= P; I++) {
            InsMinCostFlow.AddEdge(NodeIDDict["Source"], NodeIDDict["オス" + I.ToString()], 1, 0);
        }

        for (int I = 0; I <= mABInfoList.Count - 1; I++) {
            long FromNode = NodeIDDict["オス" + (I + 1).ToString()];
            InsMinCostFlow.AddEdge(FromNode, NodeIDDict["Sink"], 1, -mABInfoList[I].B);

            for (int J = 0; J <= mCDInfoList.Count - 1; J++) {
                long ToNode = NodeIDDict["メス" + (J + 1).ToString()];
                if (BanArr[J, I] == '1') {
                    InsMinCostFlow.AddEdge(FromNode, ToNode, 1, -mABInfoList[I].A);
                }
            }
        }

        for (int J = 0; J <= mCDInfoList.Count - 1; J++) {
            long FromNode = NodeIDDict["メス" + (J + 1).ToString()];
            long ToNode = NodeIDDict["Sink"];
            long Cost = mCDInfoList[J].D - mCDInfoList[J].C;
            InsMinCostFlow.AddEdge(FromNode, ToNode, 1, Cost);
        }

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

        for (int J = 0; J <= mCDInfoList.Count - 1; J++) {
            Answer -= mCDInfoList[J].D;
        }

        Console.WriteLine(-1 * Answer);
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をcharの2次元配列に設定
    ////////////////////////////////////////////////////////////////
    static char[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new char[0, 0];
        }
        int UB_X = StrList[0].Length - 1;
        int UB_Y = StrList.Count - 1;

        char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = StrList[Y][X];
            }
        }
        return WillReturn;
    }
}

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

解説

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