fork download
copy 
  1. using static IO;
  2. public class IO
  3. {
  4. public static IO Cin = new();
  5. public static StreamReader reader = new(Console.OpenStandardInput());
  6. public static StreamWriter writer = new(Console.OpenStandardOutput());
  7. public static implicit operator string(IO _) => reader.ReadLine();
  8. public static implicit operator char[](IO _) => reader.ReadLine().ToArray();
  9. public static implicit operator int(IO _) => int.Parse(reader.ReadLine());
  10. public static implicit operator double(IO _) => double.Parse(reader.ReadLine());
  11. public static implicit operator string[](IO _) => reader.ReadLine().Split();
  12. public static implicit operator int[](IO _) => Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
  13. public void Deconstruct(out int a, out int b, out int c,out int d) { int[] r = Cin; (a, b, c, d) = (r[0], r[1], r[2], r[3]); }
  14. public void Deconstruct(out int a, out int b, out int c) { int[] r = Cin; (a, b, c) = (r[0], r[1], r[2]); }
  15. public static IEnumerable<int> MakeRange(int start, int count) => Enumerable.Range(start, count);
  16. public static T[] MakeArray<T>(int count) where T : new() => MakeRange(0, count).Select(_ => new T()).ToArray();
  17. public static object? Cout { set { writer.Write(value); } }
  18. public static object? Coutln { set { writer.WriteLine(value); } }
  19. public static void Main() { Program.Coding(); writer.Flush(); }
  20. }
  21. class Program
  22. {
  23.     const int source = 0;
  24.     public static void Coding()
  25.     {
  26.         checked
  27.         {
  28.             (int nodeCount, int lineCount, int timeLimit, int minFlow) = Cin;
  29.             FlowGraph graph = new(nodeCount * (timeLimit + 1));
  30.             int sink = graph.Count - 1;
  31.             foreach (int[] input in Enumerable.Range(0, lineCount).Select(_ => (int[])Cin))
  32.             {
  33.                 int start = input[0] - 1;
  34.                 int end = input[1] - 1;
  35.                 int wave = input[2];
  36.                 for (int next = nodeCount; next < graph.Count; next += nodeCount)
  37.                 {
  38.                     graph.AddLine(start + next - nodeCount, end + next, 1, wave);
  39.                     graph.AddLine(end + next - nodeCount, start + next, 1, wave);
  40.                 }
  41.             }
  42.             for (int me = 0; me < nodeCount; me++)
  43.             {
  44.                 for (int next = me + nodeCount; next < graph.Count; next += nodeCount)
  45.                 {
  46.                     graph.AddLine(next - nodeCount, next, 614, 0);
  47.                 }
  48.             }
  49.  
  50.             int low = 1, high = 100_002;
  51.             while (low < high)
  52.             {
  53.                 int mid = (low + high) / 2;
  54.                 if (graph.GetMaxFlow(source, sink, mid) >= minFlow) high = mid;
  55.                 else low = mid + 1;
  56.             }
  57.  
  58.             Cout = high == 100_002 ? -1 : high;
  59.         }
  60.     }
  61. }
  62. class FlowLine
  63. {
  64.     public int Start { get; }
  65.     public int End { get; }
  66.     public int Capacity { get; }
  67.     public int Flow { get; set; } = 0;
  68.     public FlowLine Reverse { get; }
  69.     public int Remaining => Capacity - Flow;
  70.     public int Wave { get; }
  71.     public FlowLine(int start, int end, int capacity, int wave, FlowLine? reverse = null)
  72.     {
  73.         this.Start = start;
  74.         this.End = end;
  75.         this.Capacity = capacity;
  76.         this.Wave = wave;
  77.         this.Reverse = reverse ?? new(end, start, 0, wave, this);
  78.     }
  79. }
  80. class FlowGraph
  81. {
  82.     public FlowGraph(int size)
  83.     {
  84.         graph = MakeArray<List<FlowLine>>(Count = size);
  85.     }
  86.     public void AddLine(int start, int end, int capacity, int wave)
  87.     {
  88.         FlowLine line = new(start, end, capacity, wave);
  89.         graph[start].Add(line);
  90.         graph[end].Add(line.Reverse);
  91.     }
  92.     public int GetMaxFlow(int source, int sink, int waveLimit)
  93.     {
  94.         int totalFlow = 0;
  95.         while (true)
  96.         {
  97.             FlowLine[]? parent = new FlowLine[Count];
  98.             Queue<int> queue = new();
  99.             queue.Enqueue(source);
  100.             while (queue.TryDequeue(out int me) && parent[sink] is null)
  101.             {
  102.                 foreach (FlowLine line in graph[me])
  103.                 {
  104.                     if (line.Remaining > 0 && parent[line.End] is null && line.End != source && line.Wave <= waveLimit)
  105.                     {
  106.                         parent[line.End] = line;
  107.                         queue.Enqueue(line.End);
  108.                         if (line.End == sink) break;
  109.                     }
  110.                 }
  111.             }
  112.             if (parent[sink] is null) break;
  113.             int addFlow = int.MaxValue;
  114.             for (FlowLine? line = parent[sink]; line is not null; line = parent[line.Start])
  115.             {
  116.                 addFlow = Math.Min(addFlow, line.Remaining);
  117.             }
  118.             for (FlowLine? line = parent[sink]; line is not null; line = parent[line.Start])
  119.             {
  120.                 line.Flow += addFlow;
  121.                 line.Reverse.Flow -= addFlow;
  122.             }
  123.             totalFlow += addFlow;
  124.         }
  125.         ClearFlow();
  126.         return totalFlow;
  127.     }
  128.     public int Count { get; }
  129.     private readonly List<FlowLine>[] graph;
  130.     private void ClearFlow()
  131.     {
  132.         foreach (var lines in graph)
  133.         {
  134.             foreach (var line in lines)
  135.             {
  136.                 line.Flow = 0;
  137.             }
  138.         }
  139.     }
  140. }
Success #stdin #stdout 0.06s 31492KB
comments (?)
stdin
copy 
5 6 3 3
1 2 1
1 3 1
1 4 3
2 5 2
3 5 1
4 5 1
stdout
copy 
2
https://ideone.com/q393fl
2
language:
C# (NET 6.0)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!