using System; using System.Collections.Generic; using System.Linq; // https://yukicoder.me/problems/no/654 class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); 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\in11.txt").ToList(); //7686 } 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; // 隣接行列で枝を表現 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 mPlaneInfoList = new List(); static void Main() { List InputList = GetInputList(); int[] wkArr = { }; Action 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 = 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]; // グラフに枝を追加する 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; } } } } long CapacitySum = mPlaneInfoList.Sum(pX => pX.Capacity); // 空港で待つ分の枝 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].StaNode == mPlaneInfoList[J].StaNode) { if (mPlaneInfoList[I].StaTime <= mPlaneInfoList[J].StaTime) { mCapacityArr[I, J] = CapacitySum; } } } } for (int I = 0; I <= mPlaneInfoList.Count - 1; I++) { if (mPlaneInfoList[I].StaNode == 1) { 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 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; // 逆辺を追加する 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 NodeList; } // 幅優先探索を行い、始点から終点へのノードのListを返す // なければnullを返す static List ExecBFS() { var Queue = new Queue(); JyoutaiDef WillEnqueue; WillEnqueue.CurrNode = mSourceNode; // 始点のノードはmSourceNode WillEnqueue.NodeList = new List(); WillEnqueue.NodeList.Add(WillEnqueue.CurrNode); Queue.Enqueue(WillEnqueue); // BFSを繰り返すので、レベルの低い訪問を優先しても問題ない var VisitedSet = new HashSet(); 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(Dequeued.NodeList) { I }; Queue.Enqueue(WillEnqueue); } } return null; } }