ABC010-D 浮気予防

問題へのリンク

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

    static long mSourceNode;
    static long mSinkNode;
    static long UB;

    // 隣接行列で枝を表現
    static long[,] mCapacityArr;
    static long[,] mFlowArr;

    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 G = wkArr[1];
        long E = wkArr[2];

        if (G == 0 || E == 0) {
            Console.WriteLine(0);
            return;
        }

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

        mSourceNode = 0;
        mSinkNode = N + 1;
        UB = mSinkNode;

        mCapacityArr = new long[UB + 1, UB + 1];
        mFlowArr = new long[UB + 1, UB + 1];

        // グラフに枝を追加する
        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            mCapacityArr[wkArr[0], wkArr[1]] = 1;
            mCapacityArr[wkArr[1], wkArr[0]] = 1;
        }

        // シンクへの枝を追加
        foreach (long EachP in PArr) {
            mCapacityArr[EachP, mSinkNode] = 1;
        }

        // エドモンズ・カープで解く
        Solve();
    }

    static void Solve()
    {
        while (true) {
            List<long> NodeList = ExecBFS();
            if (NodeList == null) break;

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

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

            for (int I = 0; I <= NodeList.Count - 2; I++) {
                long FromNode = NodeList[I];
                long ToNode = NodeList[I + 1];

                CurrFlow = Math.Min(CurrFlow, mCapacityArr[FromNode, ToNode]);
            }
            //Console.WriteLine("この経路に{0}の水を流します", CurrFlow);

            for (long I = 0; I <= NodeList.Count - 2; I++) {
                long FromNode = NodeList[(int)I];
                long ToNode = NodeList[(int)I + 1];

                mCapacityArr[FromNode, ToNode] -= CurrFlow;
                mFlowArr[FromNode, ToNode] += CurrFlow;

                // 逆辺を追加する
                mCapacityArr[ToNode, FromNode] += CurrFlow;
            }
        }

        long Answer = 0;
        for (long I = 0; I <= UB; I++) {
            Answer += mFlowArr[I, UB];
        }
        Console.WriteLine(Answer);
    }

    struct JyoutaiDef
    {
        internal long CurrNode;
        internal List<long> NodeList;
    }

    // 幅優先探索を行い、始点から終点へのノードのListを返す
    // なければnullを返す
    static List<long> ExecBFS()
    {
        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrNode = mSourceNode; // 始点のノードはmSourceNode
        WillEnqueue.NodeList = new List<long>();
        WillEnqueue.NodeList.Add(WillEnqueue.CurrNode);
        Que.Enqueue(WillEnqueue);

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

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

            // 終点のノードはmSinkNode
            if (Dequeued.CurrNode == mSinkNode) {
                return Dequeued.NodeList;
            }

            for (long I = 0; I <= UB; I++) {
                long CurrCapacity = mCapacityArr[Dequeued.CurrNode, I];
                if (CurrCapacity == 0) continue;

                if (VisitedSet.Add(I) == false) continue;

                WillEnqueue.CurrNode = I;
                WillEnqueue.NodeList = new List<long>(Dequeued.NodeList) { I };
                Que.Enqueue(WillEnqueue);
            }
        }
        return null;
    }
}

解説

最小カット最大フロー定理をふまえて、
エドモンズ・カープで解いてます。