Cod sursa(job #3186018)

Utilizator beingsebiPopa Sebastian beingsebi Data 21 decembrie 2023 00:07:23
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
// #define f cin
// #define g cout
const int source = 0, dest = 204;
int cap[205][205], n;
vector<int> adj[205];
inline int flip(int poz)
{
    if (poz <= 100)
        return poz + 100;
    return poz - 100;
}
void insert_edge(int from, int to, int val)
{
    adj[from].push_back(to);
    adj[to].push_back(from);
    cap[from][to] = val;
    cap[to][from] = 0;
}
vector<int> parent;
int bfs(vector<int> &parent)
{
    parent.assign(205, -1);
    parent[source] = -2;
    queue<pair<int, int>> q;
    q.push({source, INT_MAX / 8});
    for (int ax, flow, new_flow; !q.empty();)
    {
        tie(ax, flow) = q.front();
        q.pop();
        for (int next : adj[ax])
            if (parent[next] == -1 && cap[ax][next])
            {
                parent[next] = ax;
                new_flow = min(flow, cap[ax][next]);
                if (next == dest)
                    return new_flow;
                q.push({next, new_flow});
            }
    }
    return 0;
}
int main()
{
    f >> n;
    int ans = 0;
    for (int i = 1, vin, vout; i <= n; i++)
    {
        f >> vout >> vin;
        ans += vout;
        insert_edge(source, i, vout);
        insert_edge(flip(i), dest, vin);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j)
                insert_edge(i, flip(j), 1);
    for (int new_flow, ax, prev; new_flow = bfs(parent);)
    {
        ax = dest;
        while (ax != source)
        {
            prev = parent[ax];
            cap[prev][ax] -= new_flow;
            cap[ax][prev] += new_flow;
            ax = parent[ax];
        }
    }
    g << ans << '\n';
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j && !cap[i][flip(j)])
                g << i << " " << j << '\n';
    return 0;
}