結果

問題 No.654 Air E869120
ユーザー 明智重蔵明智重蔵
提出日時 2022-06-26 15:54:32
言語 C#
(.NET 8.0.203)
結果
WA  
実行時間 -
コード長 8,857 bytes
コンパイル時間 15,115 ms
コンパイル使用メモリ 167,340 KB
実行使用メモリ 193,336 KB
最終ジャッジ日時 2024-11-16 22:30:15
合計ジャッジ時間 16,696 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 AC 70 ms
33,408 KB
testcase_31 AC 72 ms
33,408 KB
testcase_32 AC 68 ms
32,640 KB
testcase_33 AC 67 ms
32,768 KB
testcase_34 AC 66 ms
32,640 KB
testcase_35 AC 65 ms
31,468 KB
testcase_36 AC 64 ms
31,608 KB
testcase_37 AC 64 ms
31,488 KB
testcase_38 AC 65 ms
31,616 KB
testcase_39 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (89 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

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 2 5");
            WillReturn.Add("1 2 0 25 10");
            WillReturn.Add("1 2 10 40 5");
            //15
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 5 5");
            WillReturn.Add("1 2 0 15 40");
            WillReturn.Add("1 3 5 20 10");
            WillReturn.Add("2 3 30 40 20");
            WillReturn.Add("2 4 50 80 20");
            WillReturn.Add("3 4 50 70 30");
            //50
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3 4 5");
            WillReturn.Add("1 2 0 10 10");
            WillReturn.Add("1 2 10 20 3");
            WillReturn.Add("2 3 15 25 2");
            WillReturn.Add("2 3 5 15 10");
            //2
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("4 3 5");
            WillReturn.Add("1 2 0 10 100");
            WillReturn.Add("2 3 15 31 100");
            WillReturn.Add("3 4 35 45 100");
            //0
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("4 40 9");
            WillReturn.Add("2 3 90 99 43");
            WillReturn.Add("2 3 12 60 56");
            WillReturn.Add("1 3 5 9 30");
            WillReturn.Add("4 3 76 96 88");
            WillReturn.Add("2 4 76 86 66");
            WillReturn.Add("1 2 36 91 5");
            WillReturn.Add("2 1 23 82 87");
            WillReturn.Add("1 4 66 83 12");
            WillReturn.Add("1 2 2 33 72");
            WillReturn.Add("4 1 2 90 30");
            WillReturn.Add("3 2 32 84 25");
            WillReturn.Add("4 2 13 99 56");
            WillReturn.Add("4 3 49 56 94");
            WillReturn.Add("1 3 29 42 31");
            WillReturn.Add("1 2 86 88 93");
            WillReturn.Add("3 4 43 51 28");
            WillReturn.Add("3 4 5 69 60");
            WillReturn.Add("3 1 3 4 39");
            WillReturn.Add("1 4 7 73 99");
            WillReturn.Add("3 2 31 85 94");
            WillReturn.Add("1 2 89 94 94");
            WillReturn.Add("2 1 34 70 62");
            WillReturn.Add("3 4 39 94 63");
            WillReturn.Add("4 1 23 30 96");
            WillReturn.Add("3 4 41 81 29");
            WillReturn.Add("4 3 57 62 48");
            WillReturn.Add("3 2 33 54 27");
            WillReturn.Add("3 1 44 73 44");
            WillReturn.Add("3 2 50 70 19");
            WillReturn.Add("4 2 19 36 82");
            WillReturn.Add("4 2 95 97 94");
            WillReturn.Add("3 4 20 58 10");
            WillReturn.Add("1 4 4 97 33");
            WillReturn.Add("2 3 46 58 58");
            WillReturn.Add("3 1 0 80 45");
            WillReturn.Add("4 1 1 76 43");
            WillReturn.Add("3 2 16 97 9");
            WillReturn.Add("3 1 13 16 45");
            WillReturn.Add("2 4 4 16 12");
            WillReturn.Add("2 3 68 98 12");
            //240
        }
        else if (InputPattern == "Input6") {
            return System.IO.File.ReadAllLines(@"D:\CSharp\TestConsole\in35.txt").ToList();
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;
    static long mD;

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

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

    struct PlaneInfoDef
    {
        internal long StaNode;
        internal long EndNode;
        internal long StaTime;
        internal long EndTime;
        internal long Capacity;
    }
    static List<PlaneInfoDef> mPlaneInfoList = new List<PlaneInfoDef>();

    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]);
        mN = wkArr[0];
        mD = wkArr[2];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            PlaneInfoDef WillAdd;
            WillAdd.StaNode = wkArr[0];
            WillAdd.EndNode = wkArr[1];
            WillAdd.StaTime = wkArr[2];
            WillAdd.EndTime = wkArr[3];
            WillAdd.Capacity = wkArr[4];

            // ゴールノードでない場合は、乗り換え時間を足す
            if (WillAdd.EndNode != mN) {
                WillAdd.EndTime += mD;
            }

            mPlaneInfoList.Add(WillAdd);
        }

        // 開始ノードの昇順にソートしておく
        mPlaneInfoList.OrderBy(pX => pX.StaNode).ToList();

        mSourceNode = mPlaneInfoList.Count;
        mSinkNode = mSourceNode + 1;
        UB = mSinkNode;

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

        // グラフに枝を追加する
        for (int I = 0; I <= mPlaneInfoList.Count - 1; I++) {
            for (int J = 0; J <= mPlaneInfoList.Count - 1; J++) {
                if (mPlaneInfoList[I].EndNode < mPlaneInfoList[J].StaNode) {
                    break;
                }
                if (mPlaneInfoList[I].EndNode == mPlaneInfoList[J].StaNode) {
                    if (mPlaneInfoList[I].EndTime <= mPlaneInfoList[J].StaTime) {
                        mCapacityArr[I, J] = mPlaneInfoList[I].Capacity;
                    }
                }
            }
        }
        long CapacitySum = mPlaneInfoList.Sum(pX => pX.Capacity);

        for (int I = 0; I <= mPlaneInfoList.Count - 1; I++) {
            if (mPlaneInfoList[I].StaNode > 1) break;
            mCapacityArr[mSourceNode, I] = CapacitySum;
        }
        for (int I = 0; I <= mPlaneInfoList.Count - 1; I++) {
            if (mPlaneInfoList[I].EndNode == mN) {
                mCapacityArr[I, mSinkNode] += mPlaneInfoList[I].Capacity;
            }
        }

        // エドモンズ・カープで解く
        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 (int I = 0; I <= NodeList.Count - 2; I++) {
                long FromNode = NodeList[I];
                long ToNode = NodeList[I + 1];

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

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

        long Answer = 0;
        for (int 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 Queue = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrNode = mSourceNode; // 始点のノードはmSourceNode
        WillEnqueue.NodeList = new List<long>();
        WillEnqueue.NodeList.Add(WillEnqueue.CurrNode);
        Queue.Enqueue(WillEnqueue);

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

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

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

            for (int 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 };
                Queue.Enqueue(WillEnqueue);
            }
        }
        return null;
    }
}
0