Cod sursa(job #10746)

Utilizator rusRus Sergiu rus Data 29 ianuarie 2007 10:23:09
Problema Oras Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include<stdio.h>
#include<iomanip.h>
#include<math.h>
#define dim 201

typedef struct nod{
        int info;
        nod*urm;
        }*PNOD,NOD;
PNOD l[dim];
int c[dim][dim],t[dim],s[dim],f[dim][dim];
int q[dim],cr[dim];
int n,flow;
void citire();
int min(int ,int );
void edmondskarp();
void drum();
int flux();
void afisare();

int main()
{
    freopen("oras.in","r",stdin);
    freopen("oras.out","w",stdout);
    citire();
    edmondskarp();
    afisare();    
    return 0;
}
void citire()
{
     int i,j;
     scanf("%d",&n);
     for(i=0;i<=n;i++)
     c[0][i]=1;
     for(i=1;i<=n;i++)
     {
                      for(j=n+1;j<=n+n;j++)
                      if(j-n!=i)
                      c[i][j]=1;
     }
     for(i=n+1;i<=n+n;i++)
     c[i][n+n+1]=1;
     //printf("%d",n);
}
int min(int a,int b)
{
    if(a<=b ) return a;
    else
              return b;
}
void edmondskarp()
{
     while(flux())
     drum();
}
int flux()
{
    memset(s,0,sizeof(s));
    memset(t,0,sizeof(t));
    memset(cr,0,sizeof(cr));
    memset(q,0,sizeof(q));
    int p,u;
    p=u=1;
    int i,j;
    q[p]=q[u]=1;
    t[0]=0;
    s[0]=1;
    q[1]=0;
    cr[0]=32000;
    while(p<=u)
    {
               i=q[p];
               for(j=1;j<=n+n+1;j++)
               if(!s[j])
               {
                        if(c[i][j]>f[i][j])
                        {
                                           cr[j]=min(f[i][j]-c[i][j],cr[i]);
                                           q[++u]=j;
                                           t[j]=i;
                                           s[j]=1;
                                           if(j==n+n+1) return 1;
                        }
                        if(f[j][i])
                        {
                                   cr[j]=min(f[j][i],cr[i]);
                                   q[++u]=j;
                                   t[j]=-i;
                                   s[j]=1;
                                   if(j==n+n+1) return 1;
                        }
               }
    p++;
    }
    return 0;
}
void drum()
{
     int i,j;
     j=n+n+1;
     while(j)
     {
             i=abs(t[j]);
             if(t[j]>=0) f[i][j]++;
             else
                         f[j][i]--;
             j=i;
     }
     flow++;
}
void afisare()
{
     int i,j;
     
     //printf("%d ",flow);
     //if(flow!=n)
     //printf("-1");
     //else
     //{
     for(i=1;i<=n;i++)
     {
                      for(j=n+1;j<=n+n;j++)
                      printf("%d",f[i][j]);
                      printf("\n");
     }
     //}
}