Cod sursa(job #3329911)

Utilizator code_blocksSpiridon Mihnea-Andrei code_blocks Data 16 decembrie 2025 13:22:59
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int OFF = 100, NMAX = 2 * OFF + 9;
const int HIGH = 1000001;

struct graph
{
    int N, M, flow[NMAX][NMAX], cap[NMAX][NMAX];
    vector<int> A[NMAX];

    void ae(int x, int y, int c)
    {
        cap[x][y] = c;
        A[x].push_back(y);
        A[y].push_back(x);
    }
} G;

struct flow_bfs
{
    bool viz[NMAX];
    int tata[NMAX], sent_flow;

    void clear(int N)
    {
        sent_flow = HIGH;
        for(int i = 1; i <= N; i++)
            viz[i] = false, tata[i] = 0;
    }

    void find_path(graph& G, int s, int t)
    {
        clear(G.N);
        
        queue<int> q;
        q.push(s);
        viz[s] = true;

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

            for(const auto& v : G.A[n])
            {
                if(!viz[v] && G.cap[n][v] - G.flow[n][v] > 0)
                {
                    viz[v] = true;
                    q.push(v);
                    tata[v] = n;
                }
            }
        }
    }

    void run(graph& G, int s, int t)
    {
        find_path(G, s, t);

        if(viz[t] == 0)
            sent_flow = 0;
        else
        {
            vector<int> path;
            while(t != 0)
            {
                path.push_back(t);
                t = tata[t];
            }

            reverse(path.begin(), path.end());

            for(int i = 0; i < path.size() - 1; i++)
            {
                int x = path[i], y = path[i + 1];
                sent_flow = min(sent_flow, G.cap[x][y] - G.flow[x][y]);
            }

            for(int i = 0; i < path.size() - 1; i++)
            {
                int x = path[i], y = path[i + 1];
                G.flow[x][y] += sent_flow;
                G.flow[y][x] -= sent_flow;
            }
        }
    }
};

int edmonds_karp(graph& G, int s, int t)
{
    flow_bfs B;
    int max_flow = 0;
    
    do
    {
        B.run(G, s, t);
        max_flow += B.sent_flow;
    }
    while(B.sent_flow > 0);

    return max_flow;
}

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

    int dp[OFF + 1], dn[OFF + 1];

    int n, s, t;
    fin >> n;
    G.N = 2 * OFF + 2;

    s = 2 * OFF + 1;
    t = 2 * OFF + 2;

    for(int i = 1; i <= n; i++)
        fin >> dp[i] >> dn[i];

    for(int i = 1; i <= n; i++)
        for(int j = 1 + OFF; j <= n + OFF; j++)
            if(abs(i - j) != OFF)
                G.ae(i, j, 1);

    for(int i = 1; i <= n; i++)
        G.ae(s, i, dp[i]);
    
    for(int i = 1; i <= n; i++)
        G.ae(i + OFF, t, dn[i]);

    int e = edmonds_karp(G, s, t);

    fout << e << '\n';

    for(int i = 1; i <= G.N - 2; i++)
        for(int j = 1; j <= G.N - 2; j++)
            if(G.flow[i][j] > 0)
                fout << i << ' ' << j - OFF << '\n';

    fin.close();
    fout.close();

    return 0;
}