Cod sursa(job #1545771)

Utilizator algebristulFilip Berila algebristul Data 7 decembrie 2015 01:31:38
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <queue>

using namespace std;

const int SRC = 0;
const int NMAX = 202;
int DST;

vector<int> A[NMAX];
int F[NMAX][NMAX];
int C[NMAX][NMAX];
int T[NMAX];
int U[NMAX];
int In[NMAX];
int Out[NMAX];
int N;

bool drum() {
    queue<int> Q;
    memset(U, 0, sizeof(U));
    memset(T, 0, sizeof(T));
    Q.push(SRC);
    T[DST] = -1;
    U[SRC] = 1;

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        if (x == DST)
            continue;

        for (auto &y : A[x]) {
            if (F[x][y] < C[x][y] && !U[y]) {
                T[y] = x;
                U[y] = 1;
                Q.push(y);
            }
        }
    }

    if (T[DST] == -1)
        return false;

    for (auto &i : A[DST]) {
        if (!U[i])
            continue;
        if (F[i][DST] == C[i][DST])
            continue;

        int fm = 0x3f3f3f3f;

        T[DST] = i;
        int tmp = DST;
        while (tmp != SRC) {
            fm = min(fm, C[T[tmp]][tmp] - F[T[tmp]][tmp]);
            tmp = T[tmp];
        }

        tmp = DST;
        while (tmp != SRC) {
            F[T[tmp]][tmp] += fm;
            F[tmp][T[tmp]] -= fm;
            tmp = T[tmp];
        }
    }

    return true;
}

void flux() {
    while (drum());
}

int main() {
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);

    scanf("%d", &N);

    for (int i = 1; i <= N; i++) {
        scanf("%d %d", &Out[i], &In[i]);
    }

    DST = 2 * N + 1;

    for (int i = 1; i <= N; i++) {
        A[SRC].push_back(i);
        A[i].push_back(SRC);
        C[SRC][i] = Out[i];

        A[DST].push_back(i+N);
        A[i+N].push_back(DST);
        C[i+N][DST] = In[i];
    }

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

    flux();

    vector<pair<int, int> > Sol;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (F[i][j+N])
                Sol.push_back(make_pair(i, j));
        }
    }

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


    return 0;
}