Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- namespace par
- {
- class Program
- {
- static void Flow(int[,] v)
- {
- var n = v.GetLength(0);
- var f = new int[n,n];
- var del = new int[n];
- var pred = new int[n];
- var cp = new int[n];
- var mf = 0;
- do
- {
- Pmh(f, v, del, n, cp, pred);
- if (del[n - 1] < int.MaxValue)
- {
- mf += del[n - 1];
- var u = n - 1;
- while (u != 0)
- {
- var w = pred[u];
- if (cp[u] == 1)
- f[w, u] += del[n - 1];
- else
- f[u, w] -= del[n - 1];
- u = w;
- }
- }
- }
- while (del[n - 1] == int.MaxValue);
- var a = 0;
- }
- static void Pmh(int[,] f, int[,] v, int[] del, int n, int[] cp, int[] pred)
- {
- for (int i = 0; i < n; i++)
- del[i] = int.MaxValue;
- var qu = new Queue<int>();
- qu.Enqueue(0);
- pred[0] = 0;
- while (del[n-1] == int.MaxValue && qu.Count > 0)
- {
- var u = qu.Dequeue();
- for (int w = 1; w < n; w++)
- if (del[w] == int.MaxValue && f[u,w] < v[u,w])
- {
- if (v[u,w] - f[u,w] < del[u])
- del[u] = v[u,w] - f[u,w];
- qu.Enqueue(w);
- pred[w] = u;
- cp[w] = 1;
- }
- for (int w = 1; w < n; w++)
- {
- if (del[w] == int.MaxValue && f[w, u] > 0)
- {
- del[w] = Math.Min(del[u], f[w, u]);
- qu.Enqueue(w);
- pred[w] = u;
- cp[w] = -1;
- }
- }
- }
- }
- static void Main(string[] args)
- {
- var firstLine = Console.ReadLine().Split(' ');
- var k = int.Parse(firstLine[0]);
- var l = int.Parse(firstLine[1]);
- var count = int.Parse(Console.ReadLine());
- var line = new StringBuilder();
- for (int e = 0; e < count / 10.0; e++)
- {
- line.Append(Console.ReadLine());
- line.Append(' ');
- }
- var sl = line.ToString().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
- int i = 0;
- var counts = new int[k + 1];
- for (; i < k; i++)
- counts[i] = int.Parse(sl[i]);
- counts[k] = count;
- i++;
- var q = 0;
- var v = new int[l + k + 2, l + k + 2];
- for (int ku = 0; ku < v.GetLength(0); ku++)
- for (int h = 0; h < v.GetLength(1); h++)
- v[ku, h] = 0;
- while (i < count - 1)
- {
- v[q + 1, int.Parse(sl[i]) + k] = 1;
- i++;
- if (i + 1 == counts[q + 1])
- q++;
- }
- for (int u = 1; u < k + 1; u++)
- v[0, u] = 1;
- for (int u = k + 1; u < k + l + 1; u++)
- v[u, k + l + 1] = 1;
- Flow(v);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment