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