AtCoder Library Practice Contest D Maxflow

問題へのリンク

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("3 3");
            WillReturn.Add("#..");
            WillReturn.Add("..#");
            WillReturn.Add("...");
            //3
            //#<>
            //vv#
            //^^.
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mSourceNode;
    static int mSinkNode;
    static int GraphUB;

    internal struct NodeInfoDef
    {
        internal int Mod;
        internal int X;
        internal int Y;
        internal int GraphNode;
    }
    static Dictionary<int, NodeInfoDef> mNodeInfoDict = new Dictionary<int, NodeInfoDef>();
    static Dictionary<int, NodeInfoDef> mNodeInfoDictGraphNode = new Dictionary<int, NodeInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        char[,] BanArr = CreateBanArr(InputList.Skip(1));
        int UB_X = BanArr.GetUpperBound(0);
        int UB_Y = BanArr.GetUpperBound(1);

        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                if (BanArr[X, Y] == '#') continue;

                int Hash = GetHash(X, Y);
                NodeInfoDef WillAdd;
                WillAdd.Mod = (X + Y) % 2;
                WillAdd.X = X;
                WillAdd.Y = Y;
                WillAdd.GraphNode = mNodeInfoDict.Count;
                mNodeInfoDict[Hash] = WillAdd;
                mNodeInfoDictGraphNode[WillAdd.GraphNode] = WillAdd;
            }
        }

        mSourceNode = mNodeInfoDict.Count;
        mSinkNode = mSourceNode + 1;
        GraphUB = mSinkNode;

        var InsMaxFlow = new MaxFlow(mSourceNode, mSinkNode, mNodeInfoDictGraphNode);

        // グラフに枝を追加する
        foreach (var EachPair in mNodeInfoDict) {
            if (EachPair.Value.Mod != 0) continue;

            int CurrX = EachPair.Value.X;
            int CurrY = EachPair.Value.Y;

            Action<int, int> AddAct = (pTargetX, pTargetY) =>
            {
                if (pTargetX < 0 || UB_X < pTargetX) return;
                if (pTargetY < 0 || UB_Y < pTargetY) return;
                int Target = GetHash(pTargetX, pTargetY);
                if (mNodeInfoDict.ContainsKey(Target)) {
                    long FromNode = EachPair.Value.GraphNode;
                    long ToNode = mNodeInfoDict[Target].GraphNode;

                    InsMaxFlow.AddEdge(FromNode, ToNode, 1);
                }
            };
            AddAct(CurrX, CurrY - 1);
            AddAct(CurrX, CurrY + 1);
            AddAct(CurrX - 1, CurrY);
            AddAct(CurrX + 1, CurrY);
        }

        foreach (var EachPair in mNodeInfoDict) {
            if (EachPair.Value.Mod == 0) {
                InsMaxFlow.AddEdge(mSourceNode, EachPair.Value.GraphNode, 1);
            }
            else {
                InsMaxFlow.AddEdge(EachPair.Value.GraphNode, mSinkNode, 1);
            }
        }

        InsMaxFlow.DeriveMaxFlow(false);

        long PlaceCnt = InsMaxFlow.mPairDict.Count;
        foreach (var EachPair1 in InsMaxFlow.mPairDict) {
            int GraphNode1 = EachPair1.Key;
            int GraphNode2 = EachPair1.Value;

            var XList = new List<int>();
            var YList = new List<int>();
            XList.Add(mNodeInfoDictGraphNode[GraphNode1].X);
            XList.Add(mNodeInfoDictGraphNode[GraphNode2].X);
            YList.Add(mNodeInfoDictGraphNode[GraphNode1].Y);
            YList.Add(mNodeInfoDictGraphNode[GraphNode2].Y);

            XList.Sort();
            YList.Sort();

            if (XList[0] != XList[1]) {
                BanArr[XList[0], YList[0]] = '>';
                BanArr[XList[1], YList[1]] = '<';
            }
            else {
                BanArr[XList[0], YList[0]] = 'v';
                BanArr[XList[1], YList[1]] = '^';
            }
        }

        var AnswerList = new List<string>();
        AnswerList.Add(PlaceCnt.ToString());
        AnswerList.AddRange(PrintBan(BanArr));

        var sb = new System.Text.StringBuilder();
        AnswerList.ForEach(pX =>
        {
            sb.Append(pX);
            sb.AppendLine();
        });
        Console.Write(sb.ToString());
    }

    // 座標のハッシュ値を返す
    static int GetHash(int pX, int pY)
    {
        return pX * 1000 + pY;
    }

    ////////////////////////////////////////////////////////////////
    // 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;
    }

    static List<string> PrintBan(char[,] pBanArr)
    {
        var WillReturn = new List<string>();

        for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
            var sb = new System.Text.StringBuilder();
            for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
                sb.Append(pBanArr[X, Y]);
            }
            WillReturn.Add(sb.ToString());
        }
        return WillReturn;
    }
}

// 最大流のSolverクラス
#region MaxFlow
internal class MaxFlow
{
    private long mSourceNode;
    private long mSinkNode;

    private long mNextEdgeID = 0;

    // 女ノード[男ノード]なDict
    internal Dictionary<int, int> mPairDict = new Dictionary<int, int>();

    // 枝情報
    private class EdgeInfoDef
    {
        internal long EdgeID;
        internal long FromNode;
        internal long ToNode;
        internal long Capacity;
        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>();

    private Dictionary<int, Program.NodeInfoDef> mNodeInfoDictGraphNode;

    // コンストラクタ
    internal MaxFlow(long pSourceNode, long pSinkNode, Dictionary<int, Program.NodeInfoDef> pNodeInfoDictGraphNode)
    {
        mSourceNode = pSourceNode;
        mSinkNode = pSinkNode;
        mNodeInfoDictGraphNode = pNodeInfoDictGraphNode;
    }

    // グラフに辺を追加(逆辺はメソッド内部で自動追加)
    internal void AddEdge(long pFromNode, long pToNode, long pCapacity)
    {
        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.Flow = 0;
        mEdgeDict[WillAddSei.EdgeID] = WillAddSei;

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

        WillAddSei.RevPointer = WillAddRev;

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

    // 最大流を求めて返す
    internal long DeriveMaxFlow(bool pIsBFS)
    {
        long Answer = 0;
        while (true) {
            List<long> EdgeList = null;
            if (pIsBFS) {
                EdgeList = ExecBFS();
            }
            else {
                EdgeList = ExecDFS();
            }

            if (EdgeList == null) break;

            //Console.WriteLine("経路を発見しました");
            //EdgeList.ForEach(pX => Console.Write("{0},", pX));
            //Console.WriteLine();

            // 経路に流す量
            long CurrFlow = long.MaxValue;

            foreach (long EachEdge in EdgeList) {
                CurrFlow = Math.Min(CurrFlow, mEdgeDict[EachEdge].Capacity);

                int FromNode = (int)mEdgeDict[EachEdge].FromNode;
                int ToNode = (int)mEdgeDict[EachEdge].ToNode;

                // 男女のマッチングペアの更新
                if (mNodeInfoDictGraphNode.ContainsKey(FromNode) && mNodeInfoDictGraphNode.ContainsKey(ToNode)) {
                    if (mNodeInfoDictGraphNode[FromNode].Mod == 0 &&
                        mNodeInfoDictGraphNode[ToNode].Mod == 1) {
                        mPairDict[FromNode] = ToNode;
                    }
                }
            }
            //Console.WriteLine("この経路に{0}の水を流します", CurrFlow);

            foreach (long EachEdge in EdgeList) {
                mEdgeDict[EachEdge].Capacity -= CurrFlow;
                mEdgeDict[EachEdge].Flow += CurrFlow;

                // 逆辺の容量を増やす
                mEdgeDict[EachEdge].RevPointer.Capacity += CurrFlow;
            }

            Answer += CurrFlow;
        }
        return Answer;
    }

    private struct JyoutaiDef
    {
        internal long CurrNode;
        internal List<long> EdgeList;
    }

    // 幅優先探索を行い、始点から終点への枝のハッシュ値のListを返す
    // なければnullを返す
    private List<long> ExecBFS()
    {
        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrNode = mSourceNode;
        WillEnqueue.EdgeList = new List<long>();
        Que.Enqueue(WillEnqueue);

        // BFSを繰り返すので、レベルの低い訪問を優先しても問題ない
        var VisitedSet = new HashSet<long>();
        VisitedSet.Add(mSourceNode);

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            //Console.WriteLine("枝リスト");
            //Dequeued.EdgeList.ForEach(pX => Console.WriteLine(pX));

            // シンクに到達した場合
            if (Dequeued.CurrNode == mSinkNode) {
                return Dequeued.EdgeList;
            }

            long CurrNode = Dequeued.CurrNode;

            if (mEdgeInfoListDict.ContainsKey(CurrNode)) {
                foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoListDict[CurrNode]) {
                    long CurrCapacity = EachEdgeInfo.Capacity;
                    if (CurrCapacity == 0) continue;

                    if (VisitedSet.Add(EachEdgeInfo.ToNode) == false) continue;

                    WillEnqueue.CurrNode = EachEdgeInfo.ToNode;
                    WillEnqueue.EdgeList = new List<long>(Dequeued.EdgeList) { EachEdgeInfo.EdgeID };
                    Que.Enqueue(WillEnqueue);
                }
            }
        }
        return null;
    }

    // 深さ優先探索を行い、始点から終点への枝のハッシュ値のListを返す
    // なければnullを返す
    private List<long> ExecDFS()
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrNode = mSourceNode;
        WillPush.EdgeList = new List<long>();
        Stk.Push(WillPush);

        // BFSを繰り返すので、レベルの低い訪問を優先しても問題ない
        var VisitedSet = new HashSet<long>();
        VisitedSet.Add(mSourceNode);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            //Console.WriteLine("枝リスト");
            //Dequeued.EdgeList.ForEach(pX => Console.WriteLine(pX));

            // シンクに到達した場合
            if (Popped.CurrNode == mSinkNode) {
                return Popped.EdgeList;
            }

            long CurrNode = Popped.CurrNode;

            if (mEdgeInfoListDict.ContainsKey(CurrNode)) {
                foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoListDict[CurrNode]) {
                    long CurrCapacity = EachEdgeInfo.Capacity;
                    if (CurrCapacity == 0) continue;

                    if (VisitedSet.Add(EachEdgeInfo.ToNode) == false) continue;

                    WillPush.CurrNode = EachEdgeInfo.ToNode;
                    WillPush.EdgeList = new List<long>(Popped.EdgeList) { EachEdgeInfo.EdgeID };
                    Stk.Push(WillPush);
                }
            }
        }
        return null;
    }
}
#endregion

解説

チェス盤で考えると、
色が違うマス同士での二部マッチング問題に帰着できます。
なので最大流で解くことができます。