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) { int[] r = Cin; (a, b) = (r[0], r[1]); }
  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.     public static void Coding()
  24.     {
  25.         checked
  26.         {
  27.             (int nodeCount, int lineCount) = Cin;
  28.             FlowGraph graph = new(nodeCount + 1);
  29.             for (int i = 0; i < lineCount; i++)
  30.             {
  31.                 (int s, int e, int c) = Cin;
  32.                 graph.AddLine(s, e, 1, c);
  33.             }
  34.             graph.AddLine(0, 1, 2, 0);
  35.             Cout = graph.GetMaxFlow(0, nodeCount, out int cost) == 2 ? cost : -1;
  36.         }
  37.     }
  38. }
  39. class FlowLine
  40. {
  41.     public int Start { get; }
  42.     public int End { get; }
  43.     public int Capacity { get; }
  44.     public int Flow { get; set; } = 0;
  45.     public FlowLine Reverse { get; }
  46.     public int Remaining => Capacity - Flow;
  47.     public int Cost { get; }
  48.     public FlowLine(int start, int end, int capacity, int cost, FlowLine? reverse = null)
  49.     {
  50.         this.Start = start;
  51.         this.End = end;
  52.         this.Capacity = capacity;
  53.         this.Cost = cost;
  54.         this.Reverse = reverse ?? new(end, start, 0, -cost, this);
  55.     }
  56. }
  57. class FlowGraph
  58. {
  59.     public FlowGraph(int size)
  60.     {
  61.         graph = MakeArray<List<FlowLine>>(Count = size);
  62.     }
  63.     public void AddLine(int start, int end, int capacity, int cost)
  64.     {
  65.         FlowLine line = new(start, end, capacity, cost);
  66.         graph[start].Add(line);
  67.         graph[end].Add(line.Reverse);
  68.     }
  69.     public int GetMaxFlow(int source, int sink, out int cost)
  70.     {
  71.         int totalFlow = 0;
  72.         for (cost = 0; true;)
  73.         {
  74.             FlowLine?[] path = new FlowLine?[Count];
  75.             int[] dist = Enumerable.Repeat(int.MaxValue, Count).ToArray();
  76.             bool[] inQueue = new bool[Count];
  77.             Queue<int> queue = new();
  78.             dist[source] = 0;
  79.             inQueue[source] = true;
  80.             queue.Enqueue(source);
  81.             while (queue.Count > 0)
  82.             {
  83.                 int node = queue.Dequeue();
  84.                 inQueue[node] = false;
  85.                 foreach (var line in graph[node])
  86.                 {
  87.                     int nextdist = dist[node] + line.Cost;
  88.                     if (line.Remaining > 0 && dist[line.End] > nextdist)
  89.                     {
  90.                         dist[line.End] = nextdist;
  91.                         path[line.End] = line;
  92.                         if (inQueue[line.End] is false)
  93.                         {
  94.                             inQueue[line.End] = true;
  95.                             queue.Enqueue(line.End);
  96.                         }
  97.                     }
  98.                 }
  99.             }
  100.             if (path[sink] is not FlowLine sinkLine) break;
  101.             int flow = int.MaxValue;
  102.             for (FlowLine? line = sinkLine; line is not null; line = path[line.Start])
  103.             {
  104.                 flow = Math.Min(flow, line.Remaining);
  105.             }
  106.             for (FlowLine? line = sinkLine; line is not null; line = path[line.Start])
  107.             {
  108.                 line.Flow += flow;
  109.                 line.Reverse.Flow -= flow;
  110.                 cost += flow * line.Cost;
  111.             }
  112.             totalFlow += flow;
  113.         }
  114.         return totalFlow;
  115.     }
  116.     public int Count { get; }
  117.     private readonly List<FlowLine>[] graph;
  118. }
Success #stdin #stdout 0.07s 31484KB
comments (?)
stdin
copy 
4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2
stdout
copy 
6
https://ideone.com/4yG12V
6
language:
C# (NET 6.0)
created:
6 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!