Cod sursa(job #991941)

Utilizator cbanu96Banu Cristian cbanu96 Data 31 august 2013 20:52:33
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int NMAX = 102;

#define FILEIN "harta.in"
#define FILEOUT "harta.out"

vector<int> A[2*NMAX];
int cap[2*NMAX][2*NMAX];
int flow[2*NMAX][2*NMAX];
int t[2*NMAX];
int N, M, s, d;
bool mark[2*NMAX];

vector< pair<int, int> > sol;

bool bfs() {
    queue<int> Q;
    memset(mark, 0, sizeof(mark));
    Q.push(s);

    while(!Q.empty()) {
        int nod = Q.front(); Q.pop();

        if ( nod == d ) continue;
        for ( size_t j = 0; j < A[nod].size(); j++) {
            int next = A[nod][j];
            if (cap[nod][next] == flow[nod][next] || mark[next]) continue;
            mark[next] = 1;
            Q.push(next);
            t[next] = nod;
        }
    }

    return mark[d];
}

int detfmin(int nod) {
    int f = 0x3f3f3f3f;
    for ( nod = d; nod != s; nod = t[nod]) {
        f = min(f, cap[t[nod]][nod] - flow[t[nod]][nod]);
    }
    return f;
}

void rmfmin(int nod, int f) {
    for ( nod = d; nod != s; nod = t[nod]) {
        flow[t[nod]][nod] += f;
        flow[nod][t[nod]] -= f;
    }
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);
    scanf("%d", &N);
    s = 0;
    d = 2 * N + 1;
    for ( int i = 1, x, y; i <= N; i++ ) {
        scanf("%d %d", &x, &y);
        A[s].push_back(i), A[i].push_back(s), cap[s][i] = x;
        A[d].push_back(N+i), A[N+i].push_back(d), cap[N+i][d] = y;
    }

    for ( int i = 1; i <= N; i++) {
        for ( int j = 1; j <= N; j++) {
            if ( i != j ) {
                A[i].push_back(N+j);
                A[N+j].push_back(i);
                cap[i][N+j] = 1;
            }
        }
    }

    while(bfs()) {
        for ( int i = 0; i < A[d].size(); i++) {
            int nod = A[d][i];
            if (flow[nod][d] == cap[nod][d] || !mark[nod]) continue;
            t[d] = nod;

            int fminim = detfmin(nod);
            if (!fminim)
                continue;

            rmfmin(nod, fminim);
        }
    }

    for ( int i = 1; i <= N; i++) {
        for ( int j = 1; j <= N; j++) {
            if ( flow[i][N+j] ) {
                ++M;
                sol.push_back(make_pair(i, j));
            }
        }
    }

    printf("%d\n", M);
    for ( int i = 0; i < M; i++) {
        printf("%d %d\n", sol[i].first, sol[i].second);
    }
    return 0;
}