# Cod sursa(job #2123648)

Utilizator Data 6 februarie 2018 14:41:18 Taramul Nicaieri 100 cpp done Arhiva de probleme 2.9 kb
``````#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

struct graf{
int nod;
graf* next;
};

int n;

graf* g[205];
int res[205][205];

int flow;
int c[205];
int q[205];
int a,b;
int tati[205];
int dist[205];

void add(int a, int b, graf* v[])
{
graf* q = new graf;
q->nod  = b;
q->next = v[a];
v[a] = q;
}

void addd(int a, int b, graf* v[]){
}

void BFS(int k,int d){
graf*  p;
for(p = g[k]; p!=NULL; p=p->next){
if(c[p->nod] == 0 && res[p->nod][k] > 0){
++b;
q[b] = p->nod;
c[p->nod] = 1;
dist[p->nod] = d + 1;
}
}
++a;

if(b >= a)
BFS(q[a],dist[q[a]]);
}

void augment(int k){
int x = k;
int minim = 100200;

while(x != 1){
if(minim > res[tati[x]][x])
minim = res[tati[x]][x];
x = tati[x];
}
flow = flow + minim;

x = k;
while(x != 1){
res[tati[x]][x] = res[tati[x]][x] - minim;
res[x][tati[x]] = res[x][tati[x]] + minim;
x = tati[x];
}
}

int N;
void print(){
int i,j;
for(i=1;i<=N;++i){
for(j=1;j<=N;++j)
cout << res[i][j] << " ";
cout << "\n";
}
}

int main()
{
int m,x,y,z,i,j;
fin >> n ;

N = 2*n +2;
for(i=2;i<=n + 1;++i){
fin >> x >> y ;
addd(i + n,2*n + 2,g);
res[1][i] = x;
res[i + n][2*n + 2] = y;
for(j=2 + n;j<=n + n + 1 ;++j){

res[i][j] = 1;
}
}
for(i = 2, j = n + 2;i<=n + 1;++i,++j)
res[i][j] = 0;

c[N] = 1;
for(i=1;i<=N-1;++i)
c[i] = 0;
a = b = 0;
q[0] = N;

BFS(N,0);
int current = 1;
int aux;
bool liar = 1;

while(dist[1] < N){
graf*  p;
aux = 1002;
liar = 1;
for(p = g[current]; p!=NULL; p=p->next){
if(dist[p->nod]<aux && res[current][p->nod])
aux = dist[p->nod];

if(dist[p->nod] + 1 == dist[current] && res[current][p->nod]){
liar = 0;
tati[p->nod] = current;
current = p->nod;
if(current == N){
augment(N);
current = 1;
}
break;
}
}

if(liar){
dist[current] = aux + 1;
if(current != 1)
current = tati[current];
}
}

fout << flow << "\n";
for(i = 2;i<=n + 1;++i)
for(j = n + 2; j <= n + n +1; ++j)
if(res[i][j] == 0 && i != j - n)
fout << i - 1 << " " << j-n-1 << "\n";

return 0;
}
``````