Pagini recente » Cod sursa (job #2057849) | Cod sursa (job #1143966) | Cod sursa (job #2913676) | Cod sursa (job #1931889) | Cod sursa (job #518883)
Cod sursa(job #518883)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define file_in "harta.in"
#define file_out "harta.out"
#define nmax (1<<8)
int N,s,d,viz[nmax],C[nmax][nmax],F[nmax][nmax],coada[nmax],vmin,i,j;
int bfs(){
int p=0,u=1,i,g=0;
for (i=1;i<=d;++i) viz[i]=-1;
coada[1]=0;
viz[s]=0;
while(p<=u){
for(i=0;i<=d;++i){
if( C[coada[p]][i]>F[coada[p]][i] && viz[i]==-1){
if(i==d){
g=1;
continue;
}
coada[++u]=i;
viz[i]=coada[p];
}
}
p++;
}
return g;
}
int main(){
int x,y,suma;
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d", &N);
s=0;
suma=0;
d=2*N+1;
for (i=1;i<=N;++i){
scanf("%d %d", &x, &y);
suma+=x;
C[s][i]=x;
C[i+N][d]=y;
for (j=N+1;j<d;++j)
if (i!=j-N)
C[i][j]=1;
}
while(bfs()){
for (i=N+1;i<d;++i)
if (viz[i]){
viz[d]=i;
vmin=0x3f3f3f3f;
for (j=d;j!=0;j=viz[j])
vmin=min(vmin,C[viz[j]][j]-F[viz[j]][j]);
for (j=d;j!=0;j=viz[j])
F[viz[j]][j]+=vmin,
F[j][viz[j]]-=vmin;
}
}
printf("%d\n", suma);
for (i=1;i<=N;++i)
for (j=N+1;j<d;++j)
if (i!=j-N && F[i][j]>0)
printf("%d %d\n", i, j-N);
return 0;
}