Cod sursa(job #987707)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 21 august 2013 13:23:21
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <fstream>
#include <queue>
#include <vector>

#include <cstring>
using namespace std;

const int MAX_N = 102;
const int INF = 0x3f3f3f3f;

int N, sol;
int Flow[MAX_N*2][MAX_N*2], Capacity[MAX_N*2][MAX_N*2], F[MAX_N*2];
vector < int > v[MAX_N*2];
vector < pair < int, int > > a;
queue < int > Q;

inline bool BFS(int S, int D) {
    memset(F, 0, sizeof(F));
    F[S] = S;
    Q.push(S);
    while(!Q.empty()) {
        int x = Q.front();
        Q.pop();
        if(x == D)
            continue;
        for(size_t i = 0; i < v[x].size(); ++i) {
            int y = v[x][i];
            if(F[y] || Flow[x][y] >= Capacity[x][y])
                continue;
            F[y] = x, Q.push(y);
        }
    }

    return (F[D] != 0);
}

int main() {
    ifstream f("harta.in");
    ofstream g("harta.out");

    f >> N;
    int S = 2*N+1, D = 2*N+2;
    for(int i = 1, x, y; i <= N; ++i) {
        f >> x >> y;
        v[S].push_back(i), v[i].push_back(S), Capacity[S][i] += x;
        v[N+i].push_back(D), v[D].push_back(N+i), Capacity[N+i][D] += y;
    }

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            if(i != j)
                v[i].push_back(N+j), v[N+j].push_back(i), Capacity[i][N+j] += 1;

    int sum = 0;
    while(BFS(S, D)) {
        for(size_t i = 0; i < v[D].size(); ++i) {
            int y = v[D][i];
            if(!F[y] || Flow[y][D] >= Capacity[y][D])
                continue;
            F[D] = y;
            int MinFlow = INF;
            for(int x = D; x != S; x = F[x])
                MinFlow = min(MinFlow, Capacity[F[x]][x] - Flow[F[x]][x]);
            for(int x = D; x != S; x = F[x])
                Flow[F[x]][x] += MinFlow, Flow[x][F[x]] = -Flow[F[x]][x];
            sum += MinFlow;
        }
    }

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            if(Flow[i][N+j])
                ++sol, a.push_back(make_pair(i, j));

    g << sol << "\n";
    for(size_t i = 0; i < a.size(); ++i)
        g << a[i].first << " " << a[i].second << "\n";

    f.close();
    g.close();

    return 0;
}