Cod sursa(job #1598412)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 12 februarie 2016 21:33:36
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <bits/stdc++.h>

#define In(node) (node)
#define Out(node) (node+100)

using namespace std;

const int Nmax = 200 + 10;
const int inf = 0x3f3f3f3f;

int n , i , j , flow , S , D;
int dad[Nmax];
int f[Nmax][Nmax] , c[Nmax][Nmax];

vector < int > g[Nmax];
queue < int > q;

void Add(int x , int y , int capacitate)
{
    g[x].push_back(y);
    g[y].push_back(x);

    c[x][y] = capacitate;
}

bool bfs()
{
    int ok = 0; dad[S] = -1;

    for (q.push(S); q.size(); q.pop())
    {
        int node = q.front();

        for (auto &it : g[node])
            if (!dad[it] && c[node][it] > f[node][it])
            {
                if (it != D) dad[it] = node, q.push(it);
                else ok = 1;
            }
    }

    return ok;
}

void maxflow()
{
    for (bool ok = bfs() ; ok ; ok = bfs())
    {
        for (auto &it : g[D])
            if (dad[it] && c[it][D] > f[it][D])
        {
            dad[D] = it; int minn = inf;
            for (int node = D; node != S; node = dad[node])
                minn = min(minn , c[dad[node]][node] - f[dad[node]][node]);

            if (minn <= 0) continue;

            flow += minn;
            for (int node = D; node != S; node = dad[node])
                f[dad[node]][node] += minn,
                f[node][dad[node]] -= minn;
        }

        memset(dad , 0 , sizeof(dad));
    }
}

int main()
{
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);

    scanf("%d", &n); S = 201; D = 202;
    for (i = 1; i <= n; ++i)
    {
        int c1 , c2;
        scanf("%d %d", &c1, &c2);
        Add(S , Out(i) , c1);
        Add(In(i) , D , c2);
    }

    for (i = 1; i <= n; ++i)
        for (j = 1; j <= n; ++j)
            if (i != j)
                Add(Out(i) , In(j) , 1);

    maxflow();

    printf("%d\n", flow);
    for (i = 1; i <= n; ++i)
        for (j = 1; j <= n; ++j)
            if (f[Out(i)][In(j)] == 1) printf("%d %d\n", i , j);

    return 0;
}