Cod sursa(job #1443474)

Utilizator YusukeFMI Mares Medar Razvan Yusuke Data 27 mai 2015 22:59:42
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 1.29 kb
#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';
}