Wacky_rubia

Untitled

Sep 19th, 2015
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 3.59 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6.  
  7. namespace par
  8. {
  9.     class Program
  10.     {
  11.         static void Flow(int[,] v)
  12.         {
  13.             var n = v.GetLength(0);
  14.             var f = new int[n,n];
  15.             var del = new int[n];
  16.             var pred = new int[n];
  17.             var cp = new int[n];
  18.             var mf = 0;
  19.             do
  20.             {
  21.                 Pmh(f, v, del, n, cp, pred);
  22.                 if (del[n - 1] < int.MaxValue)
  23.                 {
  24.                     mf += del[n - 1];
  25.                     var u = n - 1;
  26.                     while (u != 0)
  27.                     {
  28.                         var w = pred[u];
  29.                         if (cp[u] == 1)
  30.                             f[w, u] += del[n - 1];
  31.                         else
  32.                             f[u, w] -= del[n - 1];
  33.                         u = w;
  34.                     }
  35.                 }
  36.             }
  37.             while (del[n - 1] == int.MaxValue);
  38.             var a = 0;
  39.         }
  40.  
  41.         static void Pmh(int[,] f, int[,] v, int[] del, int n, int[] cp, int[] pred)
  42.         {
  43.             for (int i = 0; i < n; i++)
  44.                 del[i] = int.MaxValue;
  45.             var qu = new Queue<int>();
  46.             qu.Enqueue(0);
  47.             pred[0] = 0;
  48.             while (del[n-1] == int.MaxValue && qu.Count > 0)
  49.             {
  50.                 var u = qu.Dequeue();
  51.                 for (int w = 1; w < n; w++)
  52.                     if (del[w] == int.MaxValue && f[u,w] < v[u,w])
  53.                     {
  54.                         if (v[u,w] - f[u,w] < del[u])
  55.                             del[u] = v[u,w] - f[u,w];
  56.                         qu.Enqueue(w);
  57.                         pred[w] = u;
  58.                         cp[w] = 1;
  59.                     }
  60.                 for (int w = 1; w < n; w++)
  61.                 {
  62.                     if (del[w] == int.MaxValue && f[w, u] > 0)
  63.                     {
  64.                         del[w] = Math.Min(del[u], f[w, u]);
  65.                         qu.Enqueue(w);
  66.                         pred[w] = u;
  67.                         cp[w] = -1;
  68.                     }
  69.                 }
  70.             }
  71.         }
  72.  
  73.         static void Main(string[] args)
  74.         {
  75.             var firstLine = Console.ReadLine().Split(' ');
  76.             var k = int.Parse(firstLine[0]);
  77.             var l = int.Parse(firstLine[1]);
  78.  
  79.             var count = int.Parse(Console.ReadLine());
  80.  
  81.             var line = new StringBuilder();
  82.             for (int e = 0; e < count / 10.0; e++)
  83.             {
  84.                 line.Append(Console.ReadLine());
  85.                 line.Append(' ');
  86.             }
  87.             var sl = line.ToString().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
  88.  
  89.             int i = 0;
  90.             var counts = new int[k + 1];
  91.             for (; i < k; i++)
  92.                 counts[i] = int.Parse(sl[i]);
  93.             counts[k] = count;
  94.  
  95.             i++;
  96.             var q = 0;
  97.             var v = new int[l + k + 2, l + k + 2];
  98.             for (int ku = 0; ku < v.GetLength(0); ku++)
  99.                 for (int h = 0; h < v.GetLength(1); h++)
  100.                     v[ku, h] = 0;
  101.  
  102.             while (i < count - 1)
  103.             {
  104.                 v[q + 1, int.Parse(sl[i]) + k] = 1;
  105.                 i++;
  106.                 if (i + 1 == counts[q + 1])
  107.                     q++;
  108.             }
  109.             for (int u = 1; u < k + 1; u++)
  110.                 v[0, u] = 1;
  111.             for (int u = k + 1; u < k + l + 1; u++)
  112.                 v[u, k + l + 1] = 1;
  113.             Flow(v);
  114.         }
  115.     }
  116. }
Advertisement
Add Comment
Please, Sign In to add comment