Cod sursa(job #3190134)

Utilizator AndreeaHzmAndreea Huzum AndreeaHzm Data 7 ianuarie 2024 00:24:37
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.4 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

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

vector<int> graph[205];
int vertices, source, destination, maxFlow, capacity[205][205], parent[205], inflow[205], outflow[205];
bool visited[205];
queue<int> bfsQueue;

bool bfs()
{
    int current, neighbor, edgeCount;
    for (int i = 1; i <= vertices; i++)
        visited[i] = false, parent[i] = 0;

    bfsQueue.push(source);
    visited[source] = true;

    while (!bfsQueue.empty())
    {
        current = bfsQueue.front();
        bfsQueue.pop();
        edgeCount = graph[current].size();

        for (int i = 0; i < edgeCount; i++)
        {
            neighbor = graph[current][i];
            if (!visited[neighbor] && capacity[current][neighbor] > 0)
            {
                visited[neighbor] = true;
                parent[neighbor] = current;
                bfsQueue.push(neighbor);
            }
        }
    }

    return visited[destination];
}

void maxflow()
{
    int i, j, flow, edgeCount = graph[destination].size();

    while (bfs())
    {
        for (i = 0; i < edgeCount; i++)
        {
            int currentNeighbor = graph[destination][i];
            if (parent[currentNeighbor] != 0 && capacity[currentNeighbor][destination] > 0)
            {
                flow = capacity[currentNeighbor][destination];

                for (j = currentNeighbor; j != source; j = parent[j])
                {
                    flow = min(flow, capacity[parent[j]][j]);
                    if (flow == 0)
                        break;
                }

                if (flow != 0)
                {
                    capacity[currentNeighbor][destination] -= flow;
                    capacity[destination][currentNeighbor] += flow;

                    for (j = currentNeighbor; j != source; j = parent[j])
                    {
                        capacity[parent[j]][j] -= flow;
                        capacity[j][parent[j]] += flow;
                    }

                    maxFlow += flow;
                }
            }
        }
    }
}

int main()
{
    int i, totalflow = 0, j, edgeCount, nn;
    fin >> vertices;
    nn = vertices;

    for (i = 1; i <= vertices; i++)
    {
        fin >> outflow[i] >> inflow[i];
        totalflow += inflow[i];
    }

    source = 2 * vertices + 1;
    destination = 2 * vertices + 2;

    for (i = 1; i <= vertices; i++)
    {
        graph[source].push_back(i);
        graph[i].push_back(source);
        graph[i + vertices].push_back(destination);
        graph[destination].push_back(i + vertices);

        capacity[source][i] = outflow[i];
        capacity[i + vertices][destination] = inflow[i];

        for (j = 1; j <= vertices; j++)
            if (i != j)
            {
                graph[i].push_back(j + vertices);
                graph[j + vertices].push_back(i);
                capacity[i][j + vertices] = 1;
            }
    }

    vertices = vertices * 2 + 2;
    maxflow();

    fout << totalflow << '\n';

    for (i = 1; i <= nn; i++)
    {
        edgeCount = graph[i].size();

        for (j = 0; j < edgeCount; j++)
            if (graph[i][j] <= 2 * nn && capacity[i][graph[i][j]] == 0)
                fout << i << " " << graph[i][j] - nn << '\n';
    }

    return 0;
}