Pagini recente » Cod sursa (job #3193352) | Cod sursa (job #2424367) | Cod sursa (job #1744311) | Cod sursa (job #1695885) | Cod sursa (job #88193)
Cod sursa(job #88193)
# include <stdio.h>
const long int MAXN=105;
long int tata[2*MAXN+1],n,muclen,source,dest,cd[2*MAXN+10],a[2*MAXN+1][2*MAXN+1];
struct {long int a,b;} muc[MAXN*MAXN+1];
void citire()
{
FILE *f=fopen("harta.in","r");
fscanf(f,"%ld",&n);
long int i,aa,bb,j;
source=0;
dest=2*n+1;
for (i=1;i<=n;i++)
{
fscanf(f,"%ld%ld",&aa,&bb);
a[source][i]=aa;
a[i+n][dest]=bb;
}
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (i!=j) a[i][j+n]=1;
fclose(f);
}
void det_drum_min(long int source)
{
long int i,j;
cd[1]=source;
tata[1]=0;
tata[dest]=0;
long int prim=1,ultim=1,sel[2*MAXN+1]={0};
sel[source]=1;
while (prim<=ultim&&!tata[dest])
{
for (i=0;i<=2*n+1;i++)
if (!sel[i]&&a[cd[prim]][i])
{
cd[++ultim]=i;
tata[i]=cd[prim];
sel[i]=1;
}
prim++;
}
}
void satureaza(long int nod)
{
long int p=tata[nod];
while (nod)
{
a[p][nod]--;
a[nod][p]++;
nod=p;
p=tata[nod];
}
}
void flux()
{
do
{
det_drum_min(source);
if (tata[dest]==0) break;
satureaza(dest);
}
while (1);
}
long int norm(long int a) {if(a>n) return a-=n;return a;}
void scrie()
{
long int nr=0,i,j;
FILE *g=fopen("harta.out","w");
for (i=1;i<=n;i++)
for (j=n+1;j<=2*n;j++)
if (a[j][i]) nr++;
fprintf(g,"%ld\n",nr);
for (i=1;i<=n;i++)
for (j=n+1;j<=2*n;j++)
if (a[j][i]) fprintf(g,"%ld %ld\n",norm(i),norm(j));
fcloseall();
}
int main()
{
citire();
flux();
scrie();
return 0;
}