yukicoder 0654 Air E869120

問題へのリンク

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 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 {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mN;
    static int mD;

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

    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.StaNode == mN) {
                continue;
            }

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

            mPlaneInfoList.Add(WillAdd);
        }

        var InsDinic = new Dinic((mN + 10) * (mPlaneInfoList.Count * 2 + 10));

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

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

        // 枝追加01 Sourceから空港1への枝
        for (int I = 0; I <= mPlaneInfoList.Count - 1; I++) {
            if (mPlaneInfoList[I].StaNode == 1) {
                InsDinic.add_edge(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) {
                        InsDinic.add_edge(I, J, mPlaneInfoList[I].Capacity);
                        break;
                    }
                }
            }
        }

        // 枝追加03 ゴールからsinkへの枝
        for (int I = 0; I <= mPlaneInfoList.Count - 1; I++) {
            if (mPlaneInfoList[I].EndNode == mN) {
                InsDinic.add_edge(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) {
                        InsDinic.add_edge(I, J, long.MaxValue);
                        break;
                    }
                }
            }
        }

        long Result = InsDinic.max_flow(mSourceNode, mSinkNode);
        Console.WriteLine(Result);
    }
}

// Dinic法
#region Dinic
internal class Dinic
{
    // 辺を表すクラス
    private class edge
    {
        internal long to;  // 行き先
        internal long cap; // 容量
        internal long rev; // 逆辺
    }

    private List<edge>[] G; // グラフの隣接リスト表現
    private long[] level;   // sからの距離
    private long[] iter;    // どこまで調べ終わったか

    // コンストラクタ(グラフのノード数を指定)
    internal Dinic(long pGraphNodeCnt)
    {
        G = new List<edge>[pGraphNodeCnt + 1];
        level = new long[pGraphNodeCnt + 1];
        iter = new long[pGraphNodeCnt + 1];
    }

    // fromからtoへ向かう容量capの辺をグラフに追加する
    internal void add_edge(long from, long to, long cap)
    {
        if (G[from] == null) G[from] = new List<edge>();
        if (G[to] == null) G[to] = new List<edge>();

        var edge1 = new edge();
        edge1.to = to;
        edge1.cap = cap;
        edge1.rev = G[to].Count;
        G[from].Add(edge1);

        var edge2 = new edge();
        edge2.to = from;
        edge2.cap = 0;
        edge2.rev = G[from].Count - 1;
        G[to].Add(edge2);
    }

    // sからの最短距離をBFSで計算する
    private void bfs(long s)
    {
        for (long i = 0; i <= level.GetUpperBound(0); i++) {
            level[i] = -1;
        }
        var que = new Queue<long>();
        level[s] = 0;
        que.Enqueue(s);
        while (que.Count > 0) {
            long v = que.Dequeue();
            for (long i = 0; G[v] != null && i < G[v].Count; i++) {
                edge e = G[v][(int)i];
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    que.Enqueue(e.to);
                }
            }
        }
    }

    // 増加パスをDFSで探す
    private long dfs(long v, long t, long f)
    {
        if (v == t) return f;
        for (; G[v] != null && iter[v] < G[v].Count; iter[v]++) {
            edge e = G[v][(int)iter[v]];
            if (e.cap > 0 && level[v] < level[e.to]) {
                long d = dfs(e.to, t, Math.Min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][(int)e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    // sからtへの最大流を求める
    internal long max_flow(long s, long t)
    {
        long flow = 0;
        for (; ; ) {
            bfs(s);
            if (level[t] < 0) return flow;
            Array.Clear(iter, 0, iter.Length);
            long f;
            while ((f = dfs(s, t, long.MaxValue)) > 0) {
                flow += f;
            }
        }
    }
}
#endregion

解説

{ノード,時間}のペアでのグラフを構築してから、最大流問題に帰着させ、
Dinic法で解いてます。