Cod sursa(job #3190215)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 7 ianuarie 2024 11:59:22
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <bits/stdc++.h>

using namespace std;

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

class Graf {
    int n;
    vector<vector<int>> L;
    vector<vector<int>> resid;
    vector<int> tata;
    bitset<1005> f;
public:
    Graf(int n, vector<vector<int>>& L, vector<vector<int>>& resid) : n(n), L(L), resid(resid) {
        tata.resize(n + 1);
        f.reset();
    }

    bool bfs(int s, int d) {
        f.reset(); f[s] = 1; tata[s] = -1;
        deque<int> c; c.push_back(s);
        while (!c.empty()) {
            int nod = c.front(); c.pop_front();
            for (int i=0; i<L[nod].size(); i++) {
                int vecin = L[nod][i];
                if (!f[vecin] && resid[nod][vecin] > 0) {
                    c.push_back(vecin);
                    f[vecin] = 1; tata[vecin] = nod;
                }
            }
        }
        return f[d];
    }

    int max_flow(int s, int d) {
        int flow = 0;
        while (bfs(s, d))
            for (int i=0; i<L[d].size(); i++) {
                int vecin = L[d][i];
                if (f[vecin] && resid[vecin][d] > 0) {
                    int path_flow = resid[vecin][d];
                    while (vecin != s) {
                        path_flow = min(path_flow, resid[tata[vecin]][vecin]);
                        vecin = tata[vecin];
                    }
                    vecin = L[d][i];
                    resid[vecin][d] -= path_flow;
                    resid[d][vecin] += path_flow;
                    while (vecin != s) {
                        resid[tata[vecin]][vecin] -= path_flow;
                        resid[vecin][tata[vecin]] += path_flow;
                        vecin = tata[vecin];
                    }
                    flow += path_flow;
                }
            }
        return flow;
    }

    void printEdges() {
        for (int i=1; i<=n/2; i++)
            for (int j=1; j<=n/2; j++)
                if (i != j && resid[i][n/2+j] == 0)
                    fout << i << " " << j << "\n";
    }

};


int main() {
    int n, x, y;
    fin >> n;
    vector<vector<int>> L(2*n+5), resid(2*n+5, vector<int>(2*n+5));
    for (int i=1; i<=n; i++) {
        fin >> x >> y;
        L[0].push_back(i);
        L[i].push_back(0);
        resid[0][i] = x;
        L[n+i].push_back(2*n+1);
        L[2*n+1].push_back(n+i);
        resid[n+i][2*n+1] = y;
    }

    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            if (i != j) {
                L[i].push_back(n+j);
                L[n+j].push_back(i);
                resid[i][n+j] = 1;
            }

    Graf g(2*n+1, L, resid);

    fout << g.max_flow(0, 2*n+1) << "\n";

    g.printEdges();

    return 0;
}