Cod sursa(job #2661122)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 21 octombrie 2020 12:55:37
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda trainingflow Marime 2.19 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,i,j,x,y,resid[205][205],tata[205];
vector<int> L[205];
deque<int> c;
bitset<205> f;

bool bfs()
{
    f.reset(); f[0] = 1; c.push_back(0); tata[0] = -1;
    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[2*n+1];
}

int main()
{
    fin >> n;
    for (i=1; i<=n; i++)
    {
        fin >> x >> y;
        L[0].push_back(i);
        L[i].push_back(0);
        resid[0][i] = x;
        L[2*n+1].push_back(n+i);
        L[n+i].push_back(2*n+1);
        resid[n+i][2*n+1] = y;
    }
    for (i=1; i<=n; i++)
        for (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;
            }
    int flow = 0;
    while (bfs())
        for (i=0; i<L[2*n+1].size(); i++)
        {
            int vecin = L[2*n+1][i];
            if (f[vecin] && resid[vecin][2*n+1] > 0)
            {
                int path_flow = resid[vecin][2*n+1];
                while (vecin != 0)
                {
                    path_flow = min(path_flow, resid[tata[vecin]][vecin]);
                    vecin = tata[vecin];
                }
                vecin = L[2*n+1][i];
                resid[vecin][2*n+1] -= path_flow;
                resid[2*n+1][vecin] += path_flow;
                while (vecin != 0)
                {
                    resid[tata[vecin]][vecin] -= path_flow;
                    resid[vecin][tata[vecin]] += path_flow;
                    vecin = tata[vecin];
                }
                flow += path_flow;
            }
        }
    fout << flow << "\n";
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            if (i != j && resid[i][n+j] == 0)
                fout << i << " " << j << "\n";
    return 0;
}