class Program
{
static void Main(string[] args)
{
int w = 0;
int m = 0, p = 0, n = 0;
int[,] C = null;
do
{
Console.WriteLine("1 - Wpisz graf ręcznie w konsoli");
Console.WriteLine("2 - Wczytaj plik z grafem");
Console.WriteLine("3 - Zakończ działanie programu");
Console.Write("Wybór opcji: ");
int.TryParse(Console.ReadLine(), out w);
bool f;
Console.WriteLine();
switch (w)
{
case 1:
f = WczytajDane(ref m, ref p, ref n, ref C);
if (f)
{
AlgorytmEdmondsaKarpa(m, p, n, C);
}
else
{
Console.WriteLine("Nie udało się poprawnie wpisać danych.");
}
break;
case 2:
f = WczytajPlik(ref m, ref p, ref n, ref C);
if (f)
{
AlgorytmEdmondsaKarpa(m, p, n, C);
}
else
{
Console.WriteLine("Nie udało się odczytać danych.");
}
break;
}
Console.WriteLine();
} while (w != 3);
}
public static void AlgorytmEdmondsaKarpa(int m, int p, int n, int[,] C)
{
int[,
] F
= new int[n
+ 2, n
+ 2]; int fmax = 0;
Queue
<int> Q
= new Queue
<int>();
int[] P
= new int[n
+ 2]; int[] CFP
= new int[n
+ 2]; while (true)
{
for (int i = 0; i <= n + 1; i++) P[i] = -1;
P[n] = -2;
CFP[n] = 9999999;
Q.Clear();
Q.Enqueue(n);
bool esc = false;
while (Q.Count != 0)
{
int v = Q.Dequeue();
for (int u = 0; u <= n + 1; u++)
{
int cp = C[v, u] - F[v, u];
if ((cp != 0) && (P[u] == -1))
{
P[u] = v;
if (CFP[v] > cp) CFP[u] = cp; else CFP[u] = CFP[v];
if (u == n + 1)
{
fmax += CFP[n + 1];
int i = u;
while (i != n)
{
v = P[i];
F[v, i] += CFP[n + 1];
F[i, v] -= CFP[n + 1];
i = v;
}
esc = true; break;
}
Q.Enqueue(u);
}
}
if (esc) break;
}
if (!esc) break;
}
Console.WriteLine();
Console.WriteLine("Wynik:");
int licznik = 0;
if (fmax > 0)
{
for (int v = m; v < n; v++)
{
bool znaleziono = false;
for (int u = 0; u < n; u++)
if ((C[v, u] == 1) && (F[v, u] == 1))
{
int nrM = u + 1;
int nrP = v - m + 1;
Console.WriteLine("Pracownik nr {0} - maszyna {1}", nrP, nrM);
znaleziono = true;
licznik++;
break;
}
if (znaleziono == false)
{
int nrP = v - m + 1;
Console.WriteLine("Pracownik nr {0} - brak maszyny", nrP);
}
}
}
Console.WriteLine("Liczba wszystkich maszyn: "+m);
Console.WriteLine("Liczba przypisanych maszyn: "+licznik);
Console.WriteLine("Liczba nieprzypisanych maszyn: "+(m-licznik));
Console.WriteLine();
Console.Write("Kliknij dowolny przycisk aby kontynuować...");
Console.ReadKey();
Console.WriteLine();
}
public static bool WczytajDane(ref int m, ref int p, ref int n, ref int[,] C)
{
Console.Write("Podaj ilość maszyn: ");
if (!int.TryParse(Console.ReadLine(), out m)) return false;
Console.Write("Podaj ilość pracowników: ");
if (!int.TryParse(Console.ReadLine(), out p)) return false;
n = p + m;
C
= new int[n
+ 2, n
+ 2];
for (int i = 0; i < m; i++)
{
C[i, n + 1] = 1;
}
for (int i = 0; i < p; i++)
{
Console.WriteLine("Podaj numery maszyn, które może obsługiwać pracownik nr {0} (Oddzielone spacją, zatwierdź enterem)", i + 1);
string[] wejscie = Console.ReadLine().Split(' ');
int tmp;
for (int j = 0; j < wejscie.Length; j++)
{
if (!int.TryParse(wejscie[j], out tmp) || tmp > m || tmp <= 0)
continue;
C[m + i, tmp - 1] = 1;
}
C[m + i, n] = 1;
}
for (int i = 0; i < p; i++)
{
C[n, i + m] = 1;
}
return true;
}
public static bool WczytajPlik(ref int m, ref int p, ref int n, ref int[,] C)
{
string nazwa = "";
Console.Write("Wpisz nazwę pliku: ");
nazwa = Console.ReadLine();
StreamReader sr = null;
try
{
sr
= new StreamReader
(nazwa
+ ".txt"); }
catch (Exception)
{
Console.WriteLine("Nie znaleziono pliku.");
return false;
}
if (sr != null)
{
if (!int.TryParse(sr.ReadLine(), out m)) return false;
if (!int.TryParse(sr.ReadLine(), out p)) return false;
n = p + m;
C
= new int[n
+ 2, n
+ 2];
for (int i = 0; i < m; i++)
{
C[i, n + 1] = 1;
}
for (int i = 0; i < p && !sr.EndOfStream; i++)
{
string[] wejscie = sr.ReadLine().Split(' ');
int tmp;
for (int j = 0; j < wejscie.Length; j++)
{
if (!int.TryParse(wejscie[j], out tmp) || tmp > m || tmp <= 0)
continue;
C[m + i, tmp - 1] = 1;
}
C[m + i, n] = 1;
}
for (int i = 0; i < p; i++)
{
C[n, i + m] = 1;
}
}
sr.Close();
return true;
}
public static void WyswietlTablice(int[,] G)
{
for (int i = 0; i < G.GetLength(0); i++)
{
for (int j = 0; j < G.GetLength(1); j++)
{
Console.Write(G[i, j] + " ");
}
Console.WriteLine();
}
Console.WriteLine();
}
public static void WyswietlTablice(int[] G)
{
for (int i = 0; i < G.GetLength(0); i++)
{
Console.Write(G[i] + " ");
}
Console.WriteLine();
Console.WriteLine();
}
}
