Cod sursa(job #253255)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 16:43:20
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
 #include<stdio.h>  
 #include<string.h>  
 #define N 205  
 int n,s,d,m;  
 int c[N][N],f[N][N],t[N],flux;  
 void citire()  
 {  
     int x,y,j;  
     for(int i=1; i<=n; i++)  
     {  
         scanf("%d%d",&x,&y);  
         c[0][i]=x;  
         c[i+n][d]=y;  
         m+=x;  
         for(j=1; j<=n; j++)  
         {  
             if(j==i)  
                 continue;  
             c[i][j+n]=1;  
         }  
     }  
 }  
 bool bfs()  
 {  
     int p,u,nod,i,q[N];  
     memset(t,0xff,sizeof(t));  
     p=u=0;  
     q[0]=s;  
     t[s]=-1;  
     for(; p<=u; p++)  
     {  
         nod=q[p];  
         for(i=0; i<=d; i++)  
         {  
             if(t[i]==-1 && c[nod][i]>f[nod][i])  
             {  
                 q[++u]=i;  
                 t[i]=nod;  
                 if(i==d)  
                     return true;  
             }  
         }  
     }  
     return false;  
 }  
 int main()  
 {  
     freopen("harta.in","r",stdin);  
     freopen("harta.out","w",stdout);  
     scanf("%d",&n);  
     d=(n<<1)+1;  
     citire();  
     int i,j;  
     while(bfs())  
     {  
         i=d;  
         while(i)  
         {  
             f[t[i]][i]++;  
             f[i][t[i]]--;  
             i=t[i];  
         }  
     }  
     printf("%d\n",m);  
     for(i=1; i<=n; i++)  
     {  
         for(j=n+1; j<d; j++)  
         {  
             if(f[i][j]>0)  
                 printf("%d %d\n",i,j-n);  
         }  
     }  
     return 0;  
}