Cod sursa(job #2421986)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 16 mai 2019 21:16:57
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <bits/stdc++.h>

using namespace std;

int c[300][300];
int ind[200], outd[200];
int n;

int viz[300];
int p[300];

vector<int> g[300];

void bfs()
{
    for(int i = 0; i <= n * 2 + 1; i++)
        p[i] = -1;
    memset(viz, 0, sizeof(viz));

    queue<int> q;
    q.push(0);
    viz[0] = 1;
    p[0] = 0;

    while(!q.empty())
    {
        int nod = q.front();
        q.pop();

        for(int v : g[nod])
        {
            if(v != 1 && !viz[v] && c[nod][v] > 0)
            {
                viz[v] = 1;
                p[v] = nod;
                q.push(v);
            }
        }
    }
}

int main() {
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);
    scanf("%d", &n);
    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &outd[i], &ind[i]);
        sum += ind[i];
    }

    for(int i = 1; i <= n; i++)
    {
        g[0].push_back(i * 2);
        g[i * 2].push_back(0);
        g[1].push_back(i * 2 + 1);
        g[i * 2 + 1].push_back(1);

        c[0][i * 2] = outd[i];
        c[i * 2 + 1][1] = ind[i];
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == j)
                continue;
            g[i * 2].push_back(j * 2 + 1);
            g[j * 2 + 1].push_back(i * 2);
            c[i * 2][j * 2 + 1] = 1;
        }
    }

    while(1)
    {
        bfs();
        int ok = 0;

        for(int v : g[1])
        {
            if(viz[v] && c[v][1] > 0)
            {
                ok = 1;
                int flow = c[v][1];
                int nod = v;
                while(p[nod] != nod)
                {
                    flow = min(flow, c[p[nod]][nod]);
                    nod = p[nod];
                }

                nod = v;

                c[v][1] -= flow;
                c[1][v] += flow;

                while(p[nod] != nod)
                {
                    c[p[nod]][nod] -= flow;
                    c[nod][p[nod]] += flow;
                    nod = p[nod];
                }
            }
        }

        if(ok == 0)
            break;
    }

    printf("%d\n", sum);
    for(int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)
                continue;
            if(c[i * 2][j * 2 + 1] != 1)
                printf("%d %d\n", i, j);
        }
    }

    return 0;
}