Pagini recente » Cod sursa (job #3171389) | Cod sursa (job #1192057) | Diferente pentru teorema-chineza-a-resturilor intre reviziile 82 si 81 | Cod sursa (job #2142024) | Cod sursa (job #159425)
Cod sursa(job #159425)
#include<stdio.h>
#include<string.h>
#define N 210
#define ABS( a ) ( (a) < 0 ) ? - a : a
int gext[N],gint[N],FLOW[N][N],CAP[N][N];
int S[N],Q[N],T[N];
int n,i,j,sursa,dest,flow=0;
void solv( int start ){
int p, u, nod;
memset(S,0,sizeof(S));
memset(T,0,sizeof(T));
p=1;
u=1;
Q[p]=start;
T[start]=-1;
S[start]=1;
while((p<=u)&&(!S[dest])){
nod=Q[p];
for(i=sursa;i<=dest;i++ )
if(!S[i])
if(CAP[nod][i] - FLOW[nod][i] > 0 ){
T[i]=nod;
u++;
Q[u]=i;
S[i]=1;
}
else
if (FLOW[i][nod] > 0 ){
T[i]=-nod;
u++;
Q[u]=i;
S[i]=1;
}
p++;
}
}
void RELAX( int xp ){
int t;
while(T[xp]!=-1){
t=ABS(T[xp]);
if(T[xp]>0)
FLOW[t][xp]++;
else
FLOW[xp][t]--;
xp=t;
}
}
int main(){
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d\n",&n);
for(i=1;i<=n;i++)
scanf("%d %d\n",&gext[i],&gint[i]);
sursa=1;
dest=2*n+2;
memset(CAP,0,sizeof(CAP) );
memset(FLOW,0,sizeof(FLOW) );
for(i=2;i<=n+1;i++)
CAP[sursa][i]=gext[i-1];
for(i=n+2;i<dest;i++)
CAP[i][dest]=gint[i-n-1];
for(i=2;i<=n+1;i++)
for(j=n+2;j<dest;j++)
CAP[i][j]=1;
for(i=2;i<=n+1;i++)
CAP[i][i+n] = 0;
flow=0;
do{
solv(sursa);
if(S[dest]){
flow++;
RELAX(dest);
}
}while(S[dest]);
printf("%d\n",flow);
for(i=2;i<=n+1;i++)
for(j=n+2;j<dest;j++)
if(FLOW[i][j])
printf("%d %d\n",i-1,j-n-1);
fclose(stdin);
fclose(stdout);
return 0;
}