Pagini recente » Cod sursa (job #2872699) | Cod sursa (job #2312001) | Cod sursa (job #2312002) | Cod sursa (job #2864677) | Cod sursa (job #1443474)
#include <fstream>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int N, S, D, M[210][210], A[210], flux;
int i,j;
int coada[500];
char viz[500];
void Read(){
f >> N;
S=0,D = 2*N+1;
for(i = 1;i <= N;i++)
for(j = 1;j <= N;j++)
M[i][j+N]=1;
for(i = 1;i <= N;i++){
f >> M[S][i] >> M[N+i][D];
M[i][i+N] = 0;
}
}
void Solve(){
bool ok = 1;
while(ok){
ok = 0;
A[S] = -1;
for(int i = 1;i <= D;i++)
viz[i] = 0;
viz[S] = 1;
int li = 1,lf= 1;
coada[1] = S;
viz[S]=1;
while(li<=lf && ok==0){
int x=coada[li++];
for(i = 0;i <= D;i++)
if(M[x][i] && viz[i]==0){
A[i] = x;
if(i == D)
ok = 1;
coada[++lf] = i;
viz[i] = 1;
}
}
if(ok){
for(i = D; A[i]!=-1; i=A[i])
--M[A[i]][i],++M[i][A[i]];
++flux;
}
}
}
int main(){
Read();
Solve();
g << flux << '\n';
for(i = 1;i <= N;i++)
for(j = 1;j <= N;j++)
if(M[j+N][i])
g << i << " " << j << '\n';
}