Pagini recente » Cod sursa (job #2112437) | Cod sursa (job #1008431) | Cod sursa (job #2006733) | Cod sursa (job #706966) | Cod sursa (job #70840)
Cod sursa(job #70840)
using namespace std;
#include<fstream>
#include<stdio.h>
#define Nmax 210
int cap[Nmax][Nmax];
int bfs[Nmax],ant[Nmax];
char viz[Nmax];
int lat[Nmax][Nmax];
int main()
{
FILE *fin=fopen("harta.in","r"),
*fout=fopen("harta.out","w");
int N,i,j,sum=0;
fscanf(fin,"%d",&N);
for(i=1;i<=N;i++)
fscanf(fin,"%d%d",&cap[i+N][2*N+1], &cap[0][i]);
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
if(i!=j)
cap[i][j+N]=1;
//flux
int li,lf,dest=2*N+1,X,F=0;
while(1)
{
li=1,lf=0;
memset(viz,0,sizeof viz);
viz[0]=1;
for(i=1;i<=N;i++)
if(cap[0][i]>0)
{
bfs[++lf]=i;
ant[lf]=0;
viz[i]=1;
}
while(li<=lf)
{
X=bfs[li];
if(X<=N)
{
for(i=N+1;i<dest;i++)
if(cap[X][i] >0 && viz[i]==0 )
{
viz[i]=1;
bfs[++lf]=i;
ant[lf]=li;
}
}
else
{
if(cap[X][dest]>0)
{
bfs[++lf]=dest;
ant[lf]=li;
break;
}
for(i=1;i<=N;i++)
if(cap[X][i]>0 && viz[i]==0)
{
viz[i]=1;
bfs[++lf]=i;
ant[lf]=li;
}
}
li++;
}
if(bfs[lf]<dest) break;
i=lf;
while(bfs[i])
{
cap [bfs[ant[i]]] [bfs[i]] --;
cap [bfs[i]] [bfs[ant[i]]] ++;
i=ant[i];
}
F++;
}
fprintf(fout,"%d\n",F);
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
if(cap[i][j+N]==0 && cap[j+N][i]==1)
{
fprintf(fout,"%d %d\n",i,j);
if(lat[i][j])
for(;;);
else
lat[i][j]++;
}
fclose(fin);
fclose(fout);
return 0;
}