ABC205-F Grid and Tokens

問題へのリンク

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

    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]);
        int Y = wkArr[0]; // Xの頂点数
        int X = wkArr[1]; // Yの頂点数
        int Rect = wkArr[2]; // 長方形の数

        var NodeNameList = new List<string>();

        for (int I = 1; I <= Y; I++) {
            NodeNameList.Add("Y" + I.ToString());
        }
        for (int I = 1; I <= X; I++) {
            NodeNameList.Add("X" + I.ToString());
        }
        for (int I = 1; I <= Rect; I++) {
            NodeNameList.Add("RectA_" + I.ToString());
            NodeNameList.Add("RectB_" + I.ToString());
        }
        NodeNameList.Add("Source");
        NodeNameList.Add("Sink");

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

        var InsMaxFlow = new MaxFlow(NodeIDDict["Source"], NodeIDDict["Sink"]);

        Action<string, string> AddEdge = (pNodeName1, pNodeName2) =>
        {
            int FromNode = NodeIDDict[pNodeName1];
            int ToNode = NodeIDDict[pNodeName2];
            InsMaxFlow.AddEdge(FromNode, ToNode, 1);
        };

        // グラフに枝を追加する
        for (int I = 1; I <= X; I++) {
            AddEdge("Source", "X" + I.ToString());
        }
        for (int I = 1; I <= Y; I++) {
            AddEdge("Y" + I.ToString(), "Sink");
        }

        int RectNo = 1;
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            int MinY = wkArr[0];
            int MaxY = wkArr[2];

            int MinX = wkArr[1];
            int MaxX = wkArr[3];

            string RectA = "RectA_" + RectNo.ToString();
            string RectB = "RectB_" + RectNo.ToString();

            for (int I = MinX; I <= MaxX; I++) {
                AddEdge("X" + I.ToString(), RectA);
            }
            AddEdge(RectA, RectB);

            for (int I = MinY; I <= MaxY; I++) {
                AddEdge(RectB, "Y" + I.ToString());
            }

            RectNo++;
        }

        long Answer = InsMaxFlow.DeriveMaxFlow();
        Console.WriteLine(Answer);
    }
}

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

    private long mNextEdgeID = 0;

    // 枝情報
    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>();

    // コンストラクタ
    internal MaxFlow(long pSourceNode, long pSinkNode)
    {
        mSourceNode = pSourceNode;
        mSinkNode = pSinkNode;
    }

    // グラフに辺を追加(逆辺はメソッド内部で自動追加)
    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()
    {
        long Answer = 0;
        while (true) {
            List<long> EdgeList = ExecBFS();
            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);
            }
            //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;
    }
}
#endregion

解説

X座標を食べ物とし、各食べ物は1つしかない
Y座標を飲み物、各飲み物は1つしかない
長方形を飲食する人

とし、飲食する人ごとに、可能な食べ物と飲み物のペアは決まっている。
最大何人が飲食できるか？
という問題に帰着させて最大流で解いてます。

アリ本の210ページに同じ問題があります。