** UVA 10806
** Problema chinezi
# Cuplaj maxim de cost minim folosind Dijkstra

** 'CC':problema/cc

** 'CC':problema/cc
 
h2. 1. Retele de transport
 
O **retea de transport** G=(V, E) este un graf orientat in care fiecarui arc (u, v) ∈ E ii este asociata o **capacitate** nenegativa c(u,v) >=0.
Vom distinge 2 varfuri importante in retea: varful **sursa S** si varful **destinatie D**.
Un flux in reteaua de mai sus este o functie f: V x V -> R care satisface urmatoarele conditii:
 
# **Restrictie de capacitate:** pentru orice u, v &#8712; V avem f(u, v)<=c(u, v)
# **Antisimetrie:** pentru orice u, v &#8712; V avem f(u, v)=-f(v, u)
# **Conservarea fluxului:** pentru orice u &#8712; V - {S, D} avem &#8721; v &#8712; V din f(u, v) = 0
 
Prima restrictie impune pur si simplu ca fluxul de la un varf la altul sa nu depaseasca valoarea capacitatii.
Antisimetria impune ca fluxul de la un varf u la un varf v sa fie egal cu opusul fluxului de la varful v la u. Astfel, fluxul de la un varf la el insusi este 0.
Conservarea fluxului impune ca _"ceea ce intra intr-un nod sa fie egal cu ceea ce iese din nod"_
 
Mai pe intelesul tuturor putem sa ne imaginam ca fiecare arc este o conducta pentru material. Fiecare conducta are o capacitate data, care este defapt ritmul maxim cu care lichidul se poate deplasa in conducta. De exemplu, printr-o teava pot curge cel mult 2000 litri de apa pe ora, sau pe un fir conductor un curent electric de maximum 20 amperi. Varfurile sunt jonctiunile conductelor si in afara varfului sursa si destinatie, materialul nu se poate acumula in nici un varf. Aceasta proprietate se numeste **conservarea fluxului** si este identica cu legea lui Kirchoff in cazul curentului electric.