Cod sursa(job #3187629)

Utilizator alexandramocanu181Mocanu Alexandra alexandramocanu181 Data 29 decembrie 2023 18:55:02
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX_NODES = 100;
const int INF = 2e9;

int capacity[MAX_NODES * 2 + 5][MAX_NODES * 2 + 5], parent[MAX_NODES * 2 + 5], nodes, source, sink;

int bfs()
{
    memset(parent, -1, sizeof(parent));
    parent[source] = -2;
    int u, v;
    queue<int> q;
    q.push(source);
    while (!q.empty())
    {
        u = q.front();
        q.pop();
        if (u == sink)
            continue;
        for (v = 0; v <= sink; v++)
            if (parent[v] == -1 && capacity[u][v] > 0)
            {
                parent[v] = u;
                q.push(v);
            }
    }
    return (parent[sink] != -1);
}

void updateFlow()
{
    int node, flow;
    flow = INF;
    for (node = sink; parent[node] != -2; node = parent[node])
        flow = min(flow, capacity[parent[node]][node]);
    for (node = sink; parent[node] != -2; node = parent[node])
    {
        capacity[parent[node]][node] -= flow;
        capacity[node][parent[node]] += flow;
    }
}

void maxFlow()
{
    int node;
    while (bfs())
        for (node = nodes + 1; node <= 2 * nodes; node++)
            if (parent[node] != -1 && capacity[node][sink] > 0)
            {
                parent[sink] = node;
                updateFlow();
            }
}

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

    int i, j, edges, x, y;
    fin >> nodes;
    edges = 0;
    sink = 2 * nodes + 1;

    for (i = 1; i <= nodes; i++)
    {
        fin >> x >> y;
        capacity[0][i] = x;
        capacity[nodes + i][sink] = y;
        edges += x;
    }

    for (i = 1; i <= nodes; i++)
        for (j = 1; j <= nodes; j++)
            if (i != j)
                capacity[i][nodes + j] = 1;

    source = 0;
    maxFlow();

    fout << edges << endl;

    for (i = 1; i <= nodes; i++)
        for (j = 1; j <= nodes; j++)
            if (i != j && capacity[i][nodes + j] == 0)
                fout << i << " " << j << endl;

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

    return 0;
}