Cod sursa(job #3190432)

Utilizator GFA03Gavrila Florin-Alexandru GFA03 Data 7 ianuarie 2024 16:34:39
Problema Taramul Nicaieri Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#include <fstream>

using namespace std;

const int UNVISITED = -1;
const int SOURCE = -2;
const int INF = INT_MAX;

int n;
vector<vector<int>> capacity;
vector<vector<int>> flow;
vector<vector<int>> adj;

int bfs(int source, int target, vector<int> &parent)
{
    fill(parent.begin(), parent.end(), UNVISITED);
    parent[source] = SOURCE;
    queue<pair<int, int>> q;
    q.push({source, INF});

    while (!q.empty())
    {
        int cur = q.front().first;
        int prevFlow = q.front().second;
        q.pop();

        for (int next : adj[cur])
        {
            if (parent[next] == UNVISITED && capacity[cur][next] > flow[cur][next])
            {
                parent[next] = cur;
                int residualFlow = capacity[cur][next] - flow[cur][next];
                int minimumFlow = min(residualFlow, prevFlow);
                if (next == target)
                    return minimumFlow;
                q.push({next, minimumFlow});
            }
        }
    }
    return 0;
}

int maxflow(int s, int t)
{
    int sumFlow = 0;
    vector<int> parent(2 * n + 2);
    int newFlow;

    while (newFlow = bfs(s, t, parent))
    {
        sumFlow += newFlow;
        int cur = t;
        while (cur != s)
        {
            int prev = parent[cur];
            flow[prev][cur] -= newFlow;
            flow[cur][prev] += newFlow;
            cur = prev;
        }
    }

    return sumFlow;
}

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

int main()
{
    fin >> n;
    int source = 0, target = 2 * n + 1;
    int paths = 0;
    capacity.resize(2 * n + 2, vector<int>(2 * n + 2));
    flow.resize(2 * n + 2, vector<int>(2 * n + 2));
    adj.resize(2 * n + 2);
    // starting from 1 as 0 will be the source node
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        // x - out degree, y - in degree
        fin >> x >> y;
        paths += x;
        capacity[source][i] = x;
        capacity[n + i][target] = y;
        adj[source].push_back(i);
        adj[i].push_back(source);
        adj[n + i].push_back(target);
        adj[target].push_back(n + i);
        for (int j = 1; j <= n; ++j)
        {
            if (i != j)
            {
                capacity[i][n + j] = 1;
                adj[i].push_back(n + j);
                adj[n + j].push_back(i);
            }
        }
    }

    int s = maxflow(source, target);
    cout << s;
    fout << paths << '\n';

    for (int i = 1; i <= n; ++i)
        for (int j = n + 1; j <= 2 * n; ++j)
            if (flow[i][j])
                fout << i << ' ' << j - n << '\n';

    return 0;
}