Pagini recente » Cod sursa (job #2009455) | Statistici Dariciuc Alexie (Alexie) | Cod sursa (job #393609) | Monitorul de evaluare | Cod sursa (job #286769)
Cod sursa(job #286769)
using namespace std;
#include <cstdio>
#include <algorithm>
#define Nmax 204
#define INF 1 << 30
int N, n, M, C[Nmax][Nmax], F[Nmax][Nmax], t, c[Nmax], j;
char T[Nmax];
void citire(){
int x, y, i;
FILE *f = fopen("harta.in", "r");
fscanf(f,"%d",&n);
for(i=1; i<=n; i++){
fscanf(f,"%d %d",&x, &y);
M+=x;
C[0][i] = x; C[i+n][ (n<<1) +1] = y;
N = 2*n + 1;
for(j=n+1; j < N; j++)
if( i != j - n )
C[i][j] = 1;
}
fclose(f);
}
int BF(){
int p, u = 1, i;
memset(T, 0xff, N * sizeof(char));
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){
c[++u] = i;
T[i] = c[p];
if( i == N ) return 1;
}
}
return 0;
}
void flux(){
N = 2*n + 1;
while( BF() )
for(t = N; t != 0; t = T[t]){
F[T[t]][t]++;
F[t][T[t]]--;
}
}
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;
}