Cod sursa(job #3128001)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 8 mai 2023 09:57:34
Problema Taramul Nicaieri Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>
// #define in cin
// #define out cout

using namespace std;

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

const int nmax = 1e2 + 5e0;

struct edge
{
    int dest, cap;
    edge *rev;
    edge(int dest = 0, int cap = 0) : dest(dest), cap(cap) {}
    void debug()
    {
        cerr << dest << ' ' << cap << '\n';
    }
};

int S = 0;
int D;
int n;
int sum;
vector<edge *> adj[nmax];
edge edges[nmax*3];
int ie=0;

void createEdge(int a, int b, int c)
{
    edges[ie++] = edge(b, c);
    edges[ie++] = edge(a, 0);
    edges[ie-2].rev = &edges[ie-1];
    edges[ie-1].rev = &edges[ie-2];
    adj[a].push_back(&edges[ie-2]);
    adj[b].push_back(&edges[ie-1]);
}

void doGraph()
{
    in >> n;
    D = 2 * n + 1;
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        in >> a >> b;
        createEdge(S, i, a);
        createEdge(i+n, D, b);
        sum += a;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i != j)
            {
                createEdge(i, n + j, 1);
            }
        }
    }
}

bool viz[nmax * 2];

bool pump(int node)
{
    //cerr << node << '\n';
    if (node == D)
        return 1;
    viz[node] = 1;
    for (auto i : adj[node])
    {
        int nxt = i->dest;
        if (!viz[nxt] && i->cap)
        {
            if (pump(nxt))
            {
                i->cap--;
                i->rev->cap++;
                return 1;
            }
        }
    }
    return 0;
}

void solve()
{
    for (int i = 0; i < sum; i++)
    {
        memset(viz, 0, sizeof viz);
        pump(S);
    }
}

void printSolution()
{
    out << sum << '\n';
    for (int i = 1; i <= n; i++)
    {
        for (auto e : adj[i])
        {
            if (e->dest > n && e->cap == 0)
            {
                out << i << ' ' << e->dest - n << '\n';
            }
        }
    }
}

int main()
{
    doGraph();
    solve();
    printSolution();
}