Cod sursa(job #428373)

Utilizator vladiiIonescu Vlad vladii Data 29 martie 2010 10:31:16
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define N_Max 101
#define INF 999999999
int N, C[205][205], F[205][205], TT[205], viz[205];
vector<int> G[205];
struct IO {
    int in, out;
} O[N_Max];

int BFS() {
    //BFS de la 1 la 2*N+2
    queue<int> Q;
    memset(viz, 0, sizeof(viz));
    memset(TT, 0, sizeof(TT));
    int p;
    viz[1]=1; Q.push(1);
    while(!Q.empty()) {
         p=Q.front(); Q.pop();
         for(vector<int>::iterator it=G[p].begin(); it!=G[p].end(); it++) {
              if(!viz[(*it)] && C[p][(*it)]>F[p][(*it)]) {
                   viz[(*it)]=1;
                   Q.push((*it));
                   TT[(*it)]=p;
                   if((*it)==2*N+2) { return 1; }
              }
         }
    }
    return 0;
}

int main() {
    FILE *f1=fopen("harta.in", "r"), *f2=fopen("harta.out", "w");
    int i, j, p, q, c;
    fscanf(f1, "%d\n", &N);
    for(i=1; i<=N; i++) {
         fscanf(f1, "%d %d\n", &O[i].out, &O[i].in);
    }
    for(i=2; i<=N+1; i++) {
         for(j=N+2; j<=2*N+1; j++) {
              if(i-1!=j-N-1) {
                   G[i].push_back(j);
                   G[j].push_back(i);
                   C[i][j]=1;
              }
         }
    }
    for(i=2; i<=N+1; i++) {
         G[1].push_back(i);
         G[i].push_back(1);
         C[1][i]=O[i-1].out;
    }
    for(i=N+2; i<=2*N+1; i++) {
         G[i].push_back(2*N+2);
         G[2*N+2].push_back(i);
         C[i][2*N+2]=O[i-N-1].in;
    }
    while(BFS()) {
         int fmin=INF;
         for(i=2*N+2; i!=1; i=TT[i]) {
              fmin=min(fmin, C[TT[i]][i]-F[TT[i]][i]);
         }
         for(i=2*N+2; i!=1; i=TT[i]) {
              F[TT[i]][i]+=fmin;
              F[i][TT[i]]-=fmin;
         }
    }
    int sol=0;
    for(i=2; i<=N+1; i++) {
         for(j=N+2; j<=2*N+1; j++) {
              if(F[i][j]) sol++;
         }
    }
    fprintf(f2, "%d\n", sol);
    for(i=2; i<=N+1; i++) {
         for(j=N+2; j<=2*N+1; j++) {
              if(F[i][j]) fprintf(f2, "%d %d\n", i-1, j-N-1);
         }
    }
    fclose(f1); fclose(f2);
    return 0;
}