Cod sursa(job #2836103)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 19 ianuarie 2022 19:15:44
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Graph
{
    vector<vector<int> > cap, G;
    vector<int> dad;
    int n;
    Graph(int _n): n(_n), dad(_n + 1)
    {
        cap = vector<vector<int> >(n + 1, vector<int>(n + 1));
        G = vector<vector<int> >(n + 1, vector<int>(n + 1));
    }

    inline void AddEdge(int x, int y, int val){
        G[x].push_back(y);
        G[y].push_back(x);
        cap[x][y] += val;
    }

    inline int BFS()
    {
        fill(dad.begin(), dad.end(), -1);
        dad[0] = 0;
        queue<int> q;
        q.push(0);
        while(!q.empty())
        {
            int nd = q.front();
            q.pop();

            if(nd == n)
                continue;

            for(auto it: G[nd])
                if(dad[it] == -1 && cap[nd][it])
                {
                    dad[it] = nd;
                    q.push(it);
                }
        }
        return dad[n];
    }

    inline int MaxFlow()
    {
        int flow(0), flowmax(0);
        while(BFS() != -1)
        {
            for(auto it: G[n])
                if(dad[it] != -1 && cap[it][n])
                {
                    dad[n] = it;
                    flow = (1 << 30);
                    int x = n;
                    while(x != 0)
                    {
                        flow = min(flow, cap[dad[x]][x]);
                        x = dad[x];
                    }

                    if(flow == 0 || flow == (1 << 30))
                        continue;

                    x = n;
                    while(x != 0)
                    {
                        cap[dad[x]][x] -= flow;
                        cap[x][dad[x]] += flow;
                        x = dad[x];
                    }
                    flowmax += flow;
                }
        }
        return flowmax;
    }
};

int main()
{
    int n;
    fin >> n;

    Graph G(2 * n + 1);
    for(int i = 1; i <= n; ++i){
        int in, out;
        fin >> in >> out;

        G.AddEdge(0, i, in);
        G.AddEdge(i + n, 2 * n + 1, out);

        for(int j = 1; j <= n; ++j)
            if(i != j)
                G.AddEdge(i, j + n, 1);
    }

    fout << G.MaxFlow() << '\n';
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(i != j && G.cap[i + n][j])
                fout << j << ' ' << i << '\n';
    return 0;
}