Pagini recente » Cod sursa (job #2413914) | Cod sursa (job #2820053) | Cod sursa (job #1797249) | Cod sursa (job #688760) | Cod sursa (job #10746)
Cod sursa(job #10746)
#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");
}
//}
}