Cod sursa(job #2655717)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 5 octombrie 2020 12:47:32
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>

using namespace std;

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

const int INF = 0x3f3f3f3f3f3f3f3f;
int n, ans;
int cap[250][250], flow[250][250], father[250];
bool use[250];
vector<vector<int>> adj;

int outer(int x)
{
    return x + n;
}

bool BFS()
{
    memset(father, INF, sizeof father);
    memset(use, false, sizeof use);

    use[0] = true;

    queue<int> q;
    q.push(0);

    while(!q.empty())
    {
        int node = q.front();
        q.pop();

        if(node == outer(n) + 1)
            continue;

        for(auto it : adj[node])
        {
            if(!use[it] && (cap[node][it] - flow[node][it] > 0))
            {
                use[it] = true;
                father[it] = node;
                q.push(it);
            }
        }
    }

    return use[outer(n) + 1];
}

int main()
{
    in >> n;

    adj.resize(2 * n + 5);

    for(int i = 1; i <= n; i++)
    {
        adj[0].push_back(i);
        adj[i].push_back(0);

        adj[outer(i)].push_back(outer(n) + 1);
        adj[outer(n) + 1].push_back(outer(i));
    }

    for(int i = 1; i <= n; i++)
    {
        int inCap, outCap;
        in >> inCap >> outCap;

        ans += inCap;

        cap[0][i] = inCap;
        cap[outer(i)][outer(n) + 1] = outCap;

        for(int j = 1; j <= n; j++)
        {
            if(i == j)
                continue;

            adj[i].push_back(outer(j));
            adj[outer(j)].push_back(i);

            cap[i][outer(j)] = 1;
        }
    }

    while(BFS())
    {
        for(auto node: adj[outer(n) + 1])
        {
            if(use[node] == true && (cap[node][outer(n) + 1] - flow[node][outer(n) + 1]))
            {
                father[outer(n) + 1] = node;

                int bottleNeck = INF;

                for(int i = outer(n) + 1; i != 0; i = father[i])
                    bottleNeck = min(bottleNeck, (cap[father[i]][i] - flow[father[i]][i]));

                for(int i = outer(n) + 1; i != 0; i = father[i])
                {
                    flow[father[i]][i] += bottleNeck;
                    flow[i][father[i]] -= bottleNeck;
                }
            }
        }
    }

    out << ans << '\n';

    for(auto node : adj[0])
    {
        if(cap[0][node] == 0)
            continue;

        for(auto it : adj[node])
            if(flow[node][it] == 1)
                out << node << ' ' << it - n << '\n';
    }

    return 0;
}