Pagini recente » Cod sursa (job #797657) | Cod sursa (job #2297992) | Cod sursa (job #1033418) | Cod sursa (job #2483432) | Cod sursa (job #2123648)
#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[]){
add(a,b,v);
add(b,a,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(1,i,g);
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){
addd(i,j,g);
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;
}