結果

問題 No.654 Air E869120
ユーザー 明智重蔵明智重蔵
提出日時 2022-07-01 04:48:13
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 351 ms / 2,000 ms
コード長 6,676 bytes
コンパイル時間 1,057 ms
コンパイル使用メモリ 109,696 KB
実行使用メモリ 32,000 KB
最終ジャッジ日時 2024-05-04 00:32:42
合計ジャッジ時間 6,688 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
20,352 KB
testcase_01 AC 43 ms
20,352 KB
testcase_02 AC 42 ms
20,224 KB
testcase_03 AC 42 ms
20,480 KB
testcase_04 AC 44 ms
20,352 KB
testcase_05 AC 44 ms
20,736 KB
testcase_06 AC 45 ms
20,224 KB
testcase_07 AC 44 ms
20,352 KB
testcase_08 AC 44 ms
20,096 KB
testcase_09 AC 43 ms
20,352 KB
testcase_10 AC 288 ms
31,056 KB
testcase_11 AC 172 ms
30,592 KB
testcase_12 AC 247 ms
31,076 KB
testcase_13 AC 289 ms
31,432 KB
testcase_14 AC 184 ms
30,464 KB
testcase_15 AC 190 ms
30,208 KB
testcase_16 AC 163 ms
31,616 KB
testcase_17 AC 351 ms
32,000 KB
testcase_18 AC 230 ms
31,616 KB
testcase_19 AC 134 ms
31,360 KB
testcase_20 AC 86 ms
28,800 KB
testcase_21 AC 90 ms
29,696 KB
testcase_22 AC 66 ms
26,752 KB
testcase_23 AC 70 ms
27,008 KB
testcase_24 AC 79 ms
28,544 KB
testcase_25 AC 64 ms
26,496 KB
testcase_26 AC 66 ms
26,880 KB
testcase_27 AC 67 ms
26,112 KB
testcase_28 AC 64 ms
26,496 KB
testcase_29 AC 63 ms
25,984 KB
testcase_30 AC 63 ms
22,784 KB
testcase_31 AC 63 ms
22,784 KB
testcase_32 AC 63 ms
23,040 KB
testcase_33 AC 62 ms
22,784 KB
testcase_34 AC 62 ms
22,528 KB
testcase_35 AC 44 ms
20,352 KB
testcase_36 AC 42 ms
20,096 KB
testcase_37 AC 41 ms
20,224 KB
testcase_38 AC 41 ms
20,608 KB
testcase_39 AC 45 ms
20,352 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;

// https://yukicoder.me/problems/no/654
class Program
{
    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();
        string wkStr;
        while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        return WillReturn;

        //return System.IO.File.ReadAllLines(@"D:\CSharp\TestConsole\in02.txt").ToList();
    }

    static int mN;
    static int mD;

    static int mSourceNode;
    static int mSinkNode;
    static int UB;

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

    struct PlaneInfoDef
    {
        internal int StaNode;
        internal int EndNode;
        internal int StaTime;
        internal int 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;
            }

            if (WillAdd.StaNode == mN) {
                continue;
            }

            mPlaneInfoList.Add(WillAdd);
        }

        // 出発時間の昇順にソートしておく
        mPlaneInfoList = mPlaneInfoList.OrderBy(pX => pX.StaTime).ToList();

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

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

        // 枝追加01 Sourceから空港1への枝
        for (int I = 0; I <= mPlaneInfoList.Count - 1; I++) {
            if (mPlaneInfoList[I].StaNode == 1) {
                mCapacityArr[mSourceNode, I] = long.MaxValue;
                break;
            }
        }

        // 枝追加02 空港から飛行機で移動する枝
        for (int I = 0; I <= mPlaneInfoList.Count - 1; I++) {
            for (int J = 0; J <= mPlaneInfoList.Count - 1; J++) {
                if (I == J) continue;
                if (mPlaneInfoList[I].EndNode == mPlaneInfoList[J].StaNode) {
                    if (mPlaneInfoList[I].EndTime <= mPlaneInfoList[J].StaTime) {
                        mCapacityArr[I, J] = mPlaneInfoList[I].Capacity;
                        break;
                    }
                }
            }
        }

        // 枝追加03 ゴールからsinkへの枝
        for (int I = 0; I <= mPlaneInfoList.Count - 1; I++) {
            if (mPlaneInfoList[I].EndNode == mN) {
                mCapacityArr[I, mSinkNode] = mPlaneInfoList[I].Capacity;
            }
        }

        // 枝追加04 空港で待つ分の枝
        for (int I = 0; I <= mPlaneInfoList.Count - 1; I++) {
            for (int J = I + 1; J <= mPlaneInfoList.Count - 1; J++) {
                if (I == J) continue;
                if (mPlaneInfoList[I].StaNode == mPlaneInfoList[J].StaNode) {
                    if (mPlaneInfoList[I].StaTime <= mPlaneInfoList[J].StaTime) {
                        mCapacityArr[I, J] = long.MaxValue;
                        break;
                    }
                }
            }
        }

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

    static void Solve()
    {
        while (true) {
            List<int> 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++) {
                int FromNode = NodeList[I];
                int ToNode = NodeList[I + 1];

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

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

                mCapacityArr[FromNode, ToNode] -= CurrFlow;
                mFlowArr[FromNode, ToNode] += CurrFlow;
                //print('from={0},to={1},water={2}'.format(u, v , m))
                //Console.WriteLine("from={0},to={1},water={2}", 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 int CurrNode;
        internal List<int> NodeList;
    }

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

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

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

            // 終点のノードは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<int>(Dequeued.NodeList) { I };
                Queue.Push(WillEnqueue);
            }
        }
        return null;
    }
}
0