Pagini recente » Cod sursa (job #2846567) | Cod sursa (job #2858247) | Cod sursa (job #2929024) | Cod sursa (job #23675) | Cod sursa (job #121181)
Cod sursa(job #121181)
#include <cstdio>
#define fin "harta.in"
#define fout "harta.out"
#define DxBG
#define FL
const int Nmax = 400;
int N,M,S,D;
int G[Nmax][Nmax],C[Nmax][Nmax],F[Nmax][Nmax];
int gradi[Nmax],grade[Nmax];
int q[Nmax],tat[Nmax];
int st,dr;
void readdata()
{
int i;
freopen(fin,"r",stdin);
scanf("%d",&N);
for (i=1;i<=N;++i)
scanf("%d%d",&grade[i],&gradi[i]);
}
void init()
{
int i,j;
S = 2*N + 1;
D = 2*N + 2;
//initializez capacitatile de la sursa la noduri
for (i=1;i<=N;++i)
{
C[S][i] = grade[i];
G[S][i] = G[i][S] = 1;
}
//initializez capacitatile de la noduri' la destinatie
for (i=1;i<=N;++i)
{
C[N+i][D] = gradi[i];
G[N+i][D] = G[D][N+i] = 1;
}
//pun capacitate 1 de la fiecare nod la fiecare nod'
for (i=1;i<=N;++i)
for (j=1;j<=N;++j)
if (i!=j)
{
C[i][N+j] = 1;
G[i][N+j] = G[N+j][i] = 1;
}
}
void bfs()
{
int i,x,j,old;
old=dr;
for (i=st;i<=old;++i)
{
x=q[i];
for (j=1;j<=2*N+2;++j)
if (G[x][j] && tat[j]==-1 && F[x][j] < C[x][j])
{
++dr;
q[dr]=j;
tat[j]=x;
}
}
st=old+1;
if (st<=dr && tat[D]==-1) bfs();
}
void flux()
{
int i,nod,add,flag=1;
init();
while (flag)
{
for (i=1;i<=2*N+2;++i)
tat[i]=-1;
st=dr=1;
q[1]=S;
tat[S]=0;
bfs();
flag=1;
if ( tat[D] == -1 )
flag=0;
else
{
//fluxul de adaugat va fi intotdeauna 1
nod=D;
while (nod!=S)
{
#ifdef DBG
printf("%d ",nod);
#endif
++F[tat[nod]][nod];
--F[nod][tat[nod]];
nod=tat[nod];
}
#ifdef DBG
printf("\n");
#endif
}
}
for (i=1;i<=N;++i)
M+=F[N+i][D];
}
void printdata()
{
int i,j;
#ifdef FL
freopen(fout,"w",stdout);
#endif
printf("%d\n",M);
for (i=1;i<=N;++i)
for (j=1;j<=N;++j)
if (F[i][N+j] == 1)
printf("%d %d\n",i,j);
}
int main()
{
readdata();
flux();
printdata();
return 0;
}