AOJ 1163 カードゲーム

問題へのリンク

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 3");
            WillReturn.Add("2 6 6 15");
            WillReturn.Add("2 3 5");
            WillReturn.Add("2 3");
            WillReturn.Add("4 9");
            WillReturn.Add("8 16 32");
            WillReturn.Add("4 2");
            WillReturn.Add("4 9 11 13");
            WillReturn.Add("5 7");
            WillReturn.Add("5 5");
            WillReturn.Add("2 3 5 1001 1001");
            WillReturn.Add("7 11 13 30 30");
            WillReturn.Add("10 10");
            WillReturn.Add("2 3 5 7 9 11 13 15 17 29");
            WillReturn.Add("4 6 10 14 18 22 26 30 34 38");
            WillReturn.Add("20 20");
            WillReturn.Add("195 144 903 63 137 513 44 626 75 473");
            WillReturn.Add("876 421 568 519 755 840 374 368 570 872");
            WillReturn.Add("363 650 155 265 64 26 426 391 15 421");
            WillReturn.Add("373 984 564 54 823 477 565 866 879 638");
            WillReturn.Add("100 100");
            WillReturn.Add("195 144 903 63 137 513 44 626 75 473");
            WillReturn.Add("876 421 568 519 755 840 374 368 570 872");
            WillReturn.Add("363 650 155 265 64 26 426 391 15 421");
            WillReturn.Add("373 984 564 54 823 477 565 866 879 638");
            WillReturn.Add("117 755 835 683 52 369 302 424 513 870");
            WillReturn.Add("75 874 299 228 140 361 30 342 750 819");
            WillReturn.Add("761 123 804 325 952 405 578 517 49 457");
            WillReturn.Add("932 941 988 767 624 41 912 702 241 426");
            WillReturn.Add("351 92 300 648 318 216 785 347 556 535");
            WillReturn.Add("166 318 434 746 419 386 928 996 680 975");
            WillReturn.Add("231 390 916 220 933 319 37 846 797 54");
            WillReturn.Add("272 924 145 348 350 239 563 135 362 119");
            WillReturn.Add("446 305 213 879 51 631 43 755 405 499");
            WillReturn.Add("509 412 887 203 408 821 298 443 445 96");
            WillReturn.Add("274 715 796 417 839 147 654 402 280 17");
            WillReturn.Add("298 725 98 287 382 923 694 201 679 99");
            WillReturn.Add("699 188 288 364 389 694 185 464 138 406");
            WillReturn.Add("558 188 897 354 603 737 277 35 139 556");
            WillReturn.Add("826 213 59 922 499 217 846 193 416 525");
            WillReturn.Add("69 115 489 355 256 654 49 439 118 961");
            WillReturn.Add("0 0");
            //3
            //1
            //0
            //4
            //9
            //18
            //85
        }
        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();

        long RestB = 0;
        long RestR = 0;

        var BList = new List<long>();
        var RList = new List<long>();

        foreach (string EachStr in InputList) {
            SplitAct(EachStr);

            if (RestB == 0 && RestR == 0) {
                RestB = wkArr[0];
                RestR = wkArr[1];
                if (RestB == 0) break;
                continue;
            }

            if (RestB > 0) {
                long[] ReadArr = EachStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
                BList.AddRange(ReadArr);

                RestB -= ReadArr.Length;
                continue;
            }
            if (RestR > 0) {
                long[] ReadArr = EachStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
                RList.AddRange(ReadArr);

                RestR -= ReadArr.Length;

                if (RestR == 0) {
                    Solve(BList.ToArray(), RList.ToArray());
                    BList.Clear();
                    RList.Clear();
                }
            }
        }
    }

    static void Solve(long[] pBArr, long[] pRArr)
    {
        long X = pBArr.Length;
        long Y = pRArr.Length;
        long SourceNode = X + Y;
        long SinkNode = SourceNode + 1;

        var InsMaxFlow = new MaxFlow(SourceNode, SinkNode);

        for (int I = 0; I <= pBArr.GetUpperBound(0); I++) {
            for (int J = 0; J <= pRArr.GetUpperBound(0); J++) {
                if (DeriveGCD(pBArr[I], pRArr[J]) > 1) {
                    InsMaxFlow.AddEdge(I, X + J, 1);
                }
            }
        }

        for (long I = 0; I <= X - 1; I++) {
            InsMaxFlow.AddEdge(SourceNode, I, 1);
        }
        for (long I = X; I <= X + Y - 1; I++) {
            InsMaxFlow.AddEdge(I, SinkNode, 1);
        }

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

    // ユークリッドの互除法で2数の最大公約数を求める
    static long DeriveGCD(long pVal1, long pVal2)
    {
        long WarareruKazu = pVal2;
        long WaruKazu = pVal1;

        while (true) {
            long Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }
}

// 最大流の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(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);
            }
            //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

解説

フォード・ファルカーソンで解いてます。