Cod sursa(job #2968693)

Utilizator alisavaAlin Sava alisava Data 21 ianuarie 2023 20:07:09
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.06 kb
// C++ implementation of Dinic's Algorithm
#include <bits/stdc++.h>

using namespace std;

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

struct Edge
{
    int v;
    int flow;
    int C;
    int rev;
};

// Residual Graph
class Graph
{
public:
    int V; // number of vertex
    vector<int> level; // stores level of a node
    vector< vector<Edge> >adj;
public:
    Graph(int V)
    {
        adj = vector<vector<Edge>>(V);
        this->V = V;
        level = vector<int>(V);
    }

    // add edge to the graph
    void addEdge(int u, int v, int C)
    {
        // Forward edge : 0 flow and C capacity
        Edge a{v, 0, C, (int) adj[v].size()};

        // Back edge : 0 flow and 0 capacity
        Edge b{u, 0, 0, (int) adj[u].size()};

        adj[u].push_back(a);
        adj[v].push_back(b); // reverse edge
    }

    bool BFS(int s, int t);

    int sendFlow(int s, int flow, int t, int ptr[]);

    int DinicMaxflow(int s, int t);
};

// Finds if more flow can be sent from s to t.
// Also assigns levels to nodes.
bool Graph::BFS(int s, int t)
{
    for (int i = 0; i < V; i++)
        level[i] = -1;

    level[s] = 0;

    list<int> q;
    q.push_back(s);

    vector<Edge>::iterator i;
    while (!q.empty())
    {
        int u = q.front();
        q.pop_front();
        for (auto &e: adj[u])
        {
            if (level[e.v] < 0 && e.flow < e.C)
            {
                level[e.v] = level[u] + 1;

                q.push_back(e.v);
            }
        }
    }
    return level[t] < 0 ? false : true;
}

int Graph::sendFlow(int u, int flow, int t, int start[])
{
    if (u == t)
        return flow;

    for (; start[u] < adj[u].size(); start[u]++)
    {
        Edge &e = adj[u][start[u]];

        if (level[e.v] == level[u] + 1 && e.flow < e.C)
        {
            int curr_flow = min(flow, e.C - e.flow);

            int temp_flow
                    = sendFlow(e.v, curr_flow, t, start);

            if (temp_flow > 0)
            {
                e.flow += temp_flow;

                adj[e.v][e.rev].flow -= temp_flow;
                return temp_flow;
            }
        }
    }
    //failed to find the target
    return 0;
}

int Graph::DinicMaxflow(int s, int t)
{
    if (s == t)
        return -1;

    int total = 0;

    while (BFS(s, t) == true)
    {
        int *start = new int[V + 1]{0};

        while (int flow = sendFlow(s, INT_MAX, t, start))
            total += flow;
    }

    return total;
}

int main()
{
    int n;
    int x, y, c;
    fin >> n;
    Graph g(n * 2  + 2);

    for (int i = 1; i <= n; i++)
    {
        fin >> x >> y;
        g.addEdge(0, i, x);
        g.addEdge(n + i, 2 * n + 1, y);
    }
    for (int i = 1; i <= n; i++)
        for (int j =  1; j <= n; j++)
        {
            if (j == i)
                continue;
            g.addEdge(i, j + n, 1);
        }
    fout << g.DinicMaxflow(0, 2 * n + 1) << "\n";
    for(int i = 1; i <= n; i++)
    {
        for(auto &edge: g.adj[i])
        {
            if (edge.flow == edge.C && edge.C > 0)
                fout << i << " " << edge.v - n<< "\n";
        }
    }
    return 0;
}