Cod sursa(job #881286)

Utilizator deneoAdrian Craciun deneo Data 17 februarie 2013 21:07:36
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

#define MAXN 2 * 110
#define INF 0x3f3f3f3f
#define FORIT(it, v) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)

int N, M, S, D, C[MAXN][MAXN], F[MAXN][MAXN], dad[MAXN], used[MAXN];
vector<int> graph[MAXN];

bool DFS() {
    queue<int> coada; coada.push(S);
    memset(used, 0, sizeof(used));

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

        used[nod] = 1;

        if (nod == D)
            return 1;

        FORIT(it, graph[nod]) {
            if (!used[*it] && C[nod][*it] - F[nod][*it]) {
                dad[*it] = nod;
                coada.push(*it);
                used[*it] = 1;
            }
        }
    }
    return 0
}

int main() {
    fin >> N;

    S = 0;
    D = 2 * N + 1;

    for (int i = 1; i <= N; ++i) {
        int a, b;
        fin >> a >> b;

        graph[S].push_back(i); graph[i].push_back(S);
        graph[i + N].push_back(D); graph[D].push_back(i + N);

        C[S][i] = a;
        C[i + N][D] = b;

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

    int sol = 0;
    while (DFS())
        FORIT(it, graph[D])
            if (dad[*it] && C[*it][D] != F[*it][D]) {
                dad[D] = *it;

                int minim = INF;
                for (int i = D; i != S; i = dad[i])
                    minim = min (minim, C[dad[i]][i] - F[dad[i]][i]);
                sol += minim;
                for (int i = D; i != S; i = dad[i]) {
                    F[dad[i]][i] += minim;
                    F[i][dad[i]] -= minim;
                }
            }

    fout << sol << "\n";
    for (int i = 1; i <= N; ++i)
        for (int j = N + 1; j <= 2 * N; ++j)
            if (F[i][j] == 1)
                fout << i << " " << j - N << "\n";

    return 0;
}