INFOMAN брой 20

{ Входни данни :
3 2 4
1 1
2 1
3 1
3 2

XVII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА

Първи ден - Задача 1. КОНФЕРЕНЦИЯ

На започващата в Конгресния център конференция за уточняване на много и 
важни въпроси касаещи две държави са изпратени M представители на 
едната и N представители на другата държава (M и N не надхвърлят 1000, 
а представителите са номерирани с числата 1,2,...,M за първата и 
1,2,...,N за втората държава). В предварителни разговори били уточнени 
K двойки от преговарящи Ц единият от едната, а другият от другата 
страна. Двойките били договорени така, че всеки от представителите да 
е включен в поне една двойка. На домакините от Конгресния център била 
поставена следната задача: да се изградят преки телефонни връзки между 
стаите на двойки от представители така, че всеки от тях да е свързан с 
поне един от представителите на другата страна, с когото има уговорка 
да преговаря. Домакините биха искали да изпълнят искането с 
изразходване на колкото може по-малко средства, като се предполага че 
прекарването на пряка линия между кои да е две стаи на Центъра има 
постоянна цена.
Напишете програма CONF.EXE, която по зададени M, N, K и договорените 
K двойки преговарящи, определя минималния брой преки телефонни линии 
които трябва да се създадат за да се удовлетвори искането на 
преговарящите.
Входният файл CONF.INP ще започва с ред съдържащ числата M, N и K, 
разделени с по един интервал. Всеки от останалите K реда на входния 
файл съдържа по една от уговорените двойки P1-P2, където P1 е 
предствител на първата, а P2 на втората държава и числата P1 и P2 са 
разделени с един интервал.
Изходният файл CONF.OUT трябва да съдържа само един ред с намереното 
минимално число телефонни линии.

РЕШЕНИЕ:

Задачата е стандартна в теорията на графите и се нарича minimum edge cover.
Minimum edge cover представлява покритието на всички върхове в дадения граф
като се използват минимален брой ребра. Решението в двуделния случай не е
никак трудно,защото е лесно да се намери напасване(matching) на двуделен граф.
Идеята е че ако разглеждаме ребтата с които покриваме като добри и лоши ребра
тогава добро ребро ще бъде такова, което не докосва други ребра вече избрани
като покриващи (това е напасване). Очевидно оптималното решение се постига
когато се максимизира броя на добрите ребра, защото те покриват едновременно
два непокрити върха, след това нищо друго не остава освен да се добавят нуж-
ното количестви лоши ребра, а именно по едно лошо ребро за всеки връх непокрит
от добро ребро.

След като имаме тази идея е много лесно да се види че формулата за броя на
ребрата е :
matched + (n + m - 2 * matched)
къдети matched е броя на ребрата в напасването.
n + m - 2 * matched
е броя на върховете, които не са покрити.

За конкретната реализация на напасването се надявам читателите да се прочели
предишните броеве на Инфоман, или поне някоя книга където алгоритъмът е
обяснен.

Има два почти аналогични начина да се намери напасването, единия е с
алтерниращо дърво а другия е с поток. Аз използвам потока. Разлика няма
защото и двата алгоритъма се свеждат до намиране на път.

Понеже ограниченията са големи трябва да се направят някои оптимизаций -
използва се списък на съседите при представянето на графа, също така пътя
не се търси рекурсивно, а се използва BFS.

Искам да поясня начина по който представям графа
-- в масива ADJ[i] са съседите на връх #i
-- броя на съседите на връх #i се записва в променливата ADJT[i].
-- G[i, j] съдържа TRUE ако има свободен капацитет в реброто (i,j).

За представянето на текущия поток, който е пуснат в графа използвам
"residual" модификацията на Ford-Fulkerson, а именно ако в графа можеше да
има ребра с капацитет > 1 тогава в G[i, j] щеше да се пази свободното място
(в flow units) в (i,j), след пускане на поток P по (i,j) трябва да се
намали капацитета на (i,j) т.е. G[i, j] := G[i, j] - P и да се увеличи
капацитета на (j,i) т.е. G[j, i] := G[j, i] + P. С тази модификация
по време на търсенето на подобрителен път можем да минаваме само по ребра
със тежести > 0, без да разглеждаме връщането на вода като специален случай.
Също така искам да спомена, че тази модификация много се ускорява ако подо-
брителния път се търси от модифицирана dijkstra. Тоест винаги да търсим
подобрителния път съдържащ най-голямо минимално ребро, така можем да
по бързо да увеличаваме потока.

Понеже графа е 0-1 т.е. тежестите са или 0 или 1. И няма никое ребро, което
да го има и в двете посоки можем да представяме дали има свободен unit в
(i,j) с един boolean, а именно G[i, j]. Също така 0-1 своиството на графа
ни дава възможност да ускорим търсенето като го реализираме с вълна.

Конструкцията на графа е следната :
-- на връх #i от множеството M му се дава номер i.
-- на връх #i от множеството N му се дава номер i + |M|
   (|M|=броя на върховете в M).
-- сорса(чешмата) е |M|+|N|+1
-- синка(мивката) е |M|+|N|+2

Jivko Ganev
}

const
  infile = 'conf.pas';
  outfile = 'conf.out';
  maxm = 1100;
  maxn = 1100;

var
  G : array [1..maxm + maxn + 2, 1..maxm + maxn + 2] of boolean;
  ADJ : array [1..maxm + maxn + 2, 1..maxm + maxn + 2] of integer;
  {списък на наследниците}
  ADJT : array [1..maxm + maxn + 2] of longint;
  {брой на наследниците}
  FL : array [1..maxm + maxn + 2] of boolean;
  {посетен ли върхът от подобрителната процедура ?}
  PR, ST : array [1..maxm + maxn + 2] of longint;
  {предшественик, и опашка за BFS}
  m, n, k, s, d, matched, ans : longint;

procedure indata;
var fin : text;
  v1, v2, i : longint;
begin
  assign(fin, infile);
  reset(fin);
  readln(fin); {Входа се чете от сорса}
  read(fin, m, n, k);
  for i := 1 to k do
  begin
    read(fin, v1, v2);
    if NOT G[v1, v2 + m] then
    begin
      G[v1, v2 + m] := true;
      inc(ADJT[v1]);
      ADJ[v1, ADJT[v1]] := v2 + m;
      inc(ADJT[v2 + m]);
      ADJ[v2 + m, ADJT[v2 + m]] := v1;
    end;
  end;
  close(fin);
  s := m + n + 1;
  d := m + n + 2;
  for i := 1 to m do
  begin
    G[s, i] := true;
    inc(ADJT[s]);
    ADJ[s, ADJT[s]] := i;
    inc(ADJT[i]);
    ADJ[i, ADJT[i]] := s;
  end;
  for i := 1 to n do
  begin
    G[i + m, d] := true;
    inc(ADJT[i + m]);
    ADJ[i + m, ADJT[i + m]] := d;
    inc(ADJT[d]);
    ADJ[d, ADJT[d]] := i + m;
  end;
end;

function augment : boolean;
var i, j, stt, sp, l : longint;
begin
  fillchar(PR, sizeof(PR), 0);
  fillchar(FL, sizeof(FL), 0);
  fillchar(ST, sizeof(ST), 0);
  ST[1] := s;
  stt := 1;
  {горен индекс в опашката}
  sp := 1;
  {долен индекс в опашката}
  FL[s] := true;
  augment := false;
  repeat
    if FL[d] then break; {има подобрителен път}
    if sp > stt then exit; {няма повече върхове в опашката}
    i := ST[sp]; inc(sp);
    for l := 1 to ADJT[i] do
    begin
      j := ADJ[i, l];
      if G[i, j] and NOT FL[j] then
      begin
        FL[j] := true;
        PR[j] := i;
        inc(stt);
        ST[stt] := j;
        {ако има 1 unit свободен капацитет в (i,j), и j-tiq връх е непосетен
	 той се слага в опашката}
      end;
    end;
  until false;
  j := d;
  i := PR[j];
  while j <> s do
  begin
    G[i, j] := NOT G[i, j]; {G[i, j] := FALSE}
    G[j, i] := NOT G[j, i]; {G[j, i] := TRUE}
    j := i;
    i := PR[j];
  end;
  augment := true;
end;

procedure solve;
begin
  while augment do inc(matched);
  ans := n + m - matched; {matched + (n + m - 2 * matched)}
end;

procedure outdata;
var fout : text;
begin
  assign(fout, outfile);
  rewrite(fout);
  writeln(fout, ans);
  close(fout);
end;

begin
  indata;
  solve;
  outdata;
end.