Pagini recente » Cod sursa (job #1657285) | Istoria paginii runda/gym1_emag_mediu_2016/clasament | Cod sursa (job #1936110) | Cod sursa (job #415625) | Cod sursa (job #290169)
Cod sursa(job #290169)
using namespace std;
#include <cstdio>
#include <algorithm>
#define Nmax 256
#define INF 1 << 30
int N, n, M, C[Nmax][Nmax], F[Nmax][Nmax], t, c[Nmax], j, i, Min;
int T[Nmax];
void citire(){
int x, y, i;
FILE *f = fopen("harta.in", "r");
fscanf(f,"%d",&n);
N = 2*n + 1;
for(i=1; i<=n; i++){
fscanf(f,"%d %d",&x, &y);
M+=x;
C[0][i] = x; C[i+n][ N] = y;
for(j=n+1; j < N; j++)
if( i != j - n )
C[i][j] = 1;
}
fclose(f);
}
int BF(){
int p, u = 1, i, ok = 0;
memset(T, 0xff, (N+2) * sizeof(int));
c[1] = 0;
T[0] = 0;
for(p = 1; p <= u; p++)
for(i = 0; i <= N; i++){
if( C[c[p]][i] > F[c[p]][i] && T[i] == -1){
if( i == N ){ok =1 ; continue;}
c[++u] = i;
T[i] = c[p];
}
}
return ok;
}
void flux(){
while( BF() ){
for(i = n+1; i < N; i++){
if( T[i] ){
T[N] = i;
for(t = N, Min = INF; t != 0; t = T[t])
Min = min (Min, C[T[t]][t] - F[T[t]][t] );
for(t = N; t != 0; t = T[t])
F[T[t]][t]+=Min ,F[t][T[t]]-=Min ;
}
}
}
}
void afisare(){
int i, j;
FILE *g = fopen("harta.out", "w");
fprintf(g,"%d\n",M);
for(i=1; i<=n; i++)
for(j = n+1; j < N ; j++)
if( i != (j - n) && F[i][j] > 0 )
fprintf(g,"%d %d\n",i, j-n);
fclose(g);
}
int main(){
citire();
flux();
afisare();
return 0;
}