Cod sursa(job #2379203)

Utilizator LucaSeriSeritan Luca LucaSeri Data 13 martie 2019 08:43:17
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 210;
const int source = 0;
const int target = 201;

int capacity[MAXN][MAXN];
int currentFlow[MAXN][MAXN];
vector< int > gr[MAXN];
int indeg[MAXN], outdeg[MAXN];
int d[MAXN];

inline void addEdge(int a, int b, int c) {
    gr[a].emplace_back(b);
    capacity[a][b] += c;
}

bool bfs() {
    memset(d, 0, sizeof d);
    queue< int > q;
    q.push(source);
    while(q.size()) {
        int node = q.front();
        q.pop();

        if(node == target) return true;
        for(auto &x : gr[node]) {
            if(!d[x] && currentFlow[node][x] < capacity[node][x]) {
                d[x] = d[node] + 1;
                q.push(x);
            }
        }
    }

    return false;
}

int dfs(int node, int flow) {
    if(node == target) return flow;
    if(!flow) return 0;
    int current = 0;
    for(auto &x : gr[node]) {
        if(d[x] != d[node] + 1) continue;
        auto pa = dfs(x, min(flow, capacity[node][x] - currentFlow[node][x]));
        currentFlow[node][x] += pa;
        currentFlow[x][node] -= pa;
        flow -= pa;
        current += pa;
    }

    return current;
}

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

    int n;
    f >> n;

    for(int i = 1; i <= n; ++i) {
        f >> outdeg[i] >> indeg[i];
        addEdge(source, i, outdeg[i]);
        addEdge(i + 100, target, indeg[i]);
        for(int j = 1; j <= 100; ++j) {
            if(i == j) continue;
            addEdge(i, 100+j, 1);
            addEdge(100+j, i, 0);
        }
    }

    int ans = 0;
    while(bfs()) {
        ans += dfs(source, 1e9);
    }

    g << ans << '\n';
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(currentFlow[i][100+j]) g << i << ' ' << j << '\n';
        }
    }
    return 0;
}