Cod sursa(job #2098467)

Utilizator amaliarebAmalia Rebegea amaliareb Data 2 ianuarie 2018 21:02:04
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
const int MaxN = 205;
int n, m, s, d, flow[MaxN][MaxN], cap[MaxN][MaxN], from[MaxN];

bool bfs()
{
    queue<int> q;
    bool viz[MaxN];
    memset(viz, 0, sizeof(viz));
    memset(from, 0, sizeof(from));
    q.push(s);
    viz[s] = 1;
    while (!q.empty() && !viz[d])
    {
        int node = q.front();
        for (int son = 1; son <= d; ++son)
            if (son != node && !viz[son] && flow[node][son] < cap[node][son])
            {
                from[son] = node;
                viz[son] = 1;
                q.push(son);
            }
        q.pop();
    }
    return viz[d];
}

int main()
{
    f >> n;
    s = 2 * n + 3;
    d = 2 * n + 2;
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
        {
            cap[2 * i][2 * j + 1] = cap[2 * j][2 * i + 1] = 1;
        }
    for (int i = 1; i <= n; ++i)
    {
        int a, b;
        f >> a >> b;
        m += a;
        cap[2 * i + 1][d] = b;
        cap[s][2 * i] = a;
    }
    while (bfs())
    {
        for (int i = 1; i <= s; ++i)
            if (from[i] && flow[i][d] < cap[i][d])
            {
                from[d] = i;
                int node = d, mini = 10000;
                while (from[node])
                {
                    mini = min(mini, cap[from[node]][node] - flow[from[node]][node]);
                    node = from[node];
                }
                node = d;
                while (from[node])
                {
                    flow[from[node]][node] += mini;
                    flow[node][from[node]] -= mini;
                    node = from[node];
                }
            }
    }
    g << m <<'\n';
    for (int i = 1; i < d; ++i)
        for (int j = 1; j < d; ++j) if (flow[i][j] > 0) g << i / 2 << ' ' << j / 2 << '\n';
    return 0;
}