Cod sursa(job #2207431)

Utilizator MaligMamaliga cu smantana Malig Data 25 mai 2018 18:03:12
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <bits/stdc++.h>

using namespace std;

#if 1
    #define pv(x) cout<<#x<<" = "<<(x)<<"; ";cout.flush()
    #define pn cout<<endl
#else
    #define pv(x)
    #define pn
#endif

#ifdef INFOARENA
    ifstream in("harta.in");
    ofstream out("harta.out");
#else
    #define in cin
    #define out cout
#endif

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define pb push_back
#define mp make_pair
const int NMax = 2e2 + 5;
const ll inf_ll = 1e18 + 5;
const int inf_int = 1e9 + 5;
const int mod = 100003;
using zint = int;

int cap[NMax][NMax], prv[NMax];
bool vis[NMax];
vector<int> adj[NMax];

bool bfs(int source, int dest) {
    memset(vis, 0, sizeof(vis));
    memset(prv, 0, sizeof(prv));
 
    queue<int> Q;
    Q.push(source);
    while (Q.size()) {
        int curr = Q.front(); Q.pop();
 
        if (curr == dest) {
            return true;
        }
 
        for (int nxt : adj[curr]) {
            if (prv[nxt] || !cap[curr][nxt]) {
                continue;
            }
 
            prv[nxt] = curr;
            Q.push(nxt);
        }
    }
 
    return false;
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);

    int N;
    in >> N;
    int source = 2*N + 1, dest = 2*N + 2;
    vector< pair<int,int> > deg(N+1);
    for (int i = 1; i <= N; ++i) {
        in >> deg[i].first >> deg[i].second;

        cap[source][i] += deg[i].first;
        adj[source].pb(i);
        adj[i].pb(source);

        cap[i + N][dest] += deg[i].second;
        adj[dest].pb(i + N);
        adj[i + N].pb(dest);
    }

    for (int i = 1; i <= N; ++i) {
        for (int j = N + 1; j <= 2*N; ++j) {
            if (i == j - N) {
                continue;
            }

            cap[i][j] += 1;
            adj[i].pb(j);
            adj[j].pb(i);
        }
    }

    while (bfs(source, dest)) {
        int node = dest;
        int minFlow = inf_int;
        while (node != source) {
            minFlow = min(minFlow, cap[prv[node]][node]);
            node = prv[node];
        }
 
        node = dest;
        while (node != source) {
            cap[prv[node]][node] -= minFlow;
            cap[node][prv[node]] += minFlow;
            node = prv[node];
        }
    }

    for (int i = 1; i <= N; ++i) {
        for (int j = N + 1; j <= 2*N; ++j) {
            if (cap[i][j] == 0) {
                out << i << ' ' << j - N << '\n';
            }
        }
    }
 
    // out << maxFlow << '\n';

    return 0;
}