Cod sursa(job #301682)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 8 aprilie 2009 13:01:52
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include<stdio.h>

FILE *fin=fopen("harta.in","r"),
    *fout=fopen("harta.out","w");

int N,S,D,M[210][210],A[210],flux;
//int coada[500];
char viz[500];
struct elem{int inf;elem* next;};
typedef elem* coada;
coada Q,Qf;

int main(){
    fscanf(fin,"%d",&N);
    S=0,D=N+N+1;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            M[i][j+N]=1;
    for(int i=1;i<=N;i++){
        fscanf(fin,"%d %d",&M[S][i],&M[N+i][D]);
        M[i][i+N]=0;
    }

    int ok=1;
    while(ok){
        ok=0;
        A[S]=-1;
        for(int i=1;i<=D;i++)
            viz[i]=0;

        Q=Qf=new elem;
        Q->inf=S;
        viz[S]=1;
        while(Q && ok==0){
            int x=Q->inf;

            for(int i=0;i<=D;i++)
                if(M[x][i] && viz[i]==0){
                    A[i]=x;
                    if(i==D)
                        ok=1;
                    Qf->next=new elem;
                    Qf=Qf->next;
                    Qf->next=NULL;
                    Qf->inf=i;
                    viz[i]=1;
                }
            coada aux=Q;
            Q=Q->next;
            delete aux;
        }
  /*      int li=1,lf=1;
        coada[1]=S;
        viz[S]=1;
        while(li<=lf && ok==0){
            int x=coada[li++];

            for(int 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(int i=D;A[i]!=-1;i=A[i])
                --M[A[i]][i],++M[i][A[i]];
            ++flux;
        }

    }

    fprintf(fout,"%d\n",flux);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            if(M[j+N][i])
                fprintf(fout,"%d %d\n",i,j);
    fclose(fin);
    fclose(fout);
    return 0;
}