Cod sursa(job #13269)

Utilizator victorsbVictor Rusu victorsb Data 6 februarie 2007 01:18:23
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <cstdio>
#include <vector>

using namespace std;

#define Nmax 256
#define pb push_back
#define sz(a) int((a).size())

int n, i, j, s, d, flux, ct;
int grin[Nmax], grout[Nmax], cap[Nmax][Nmax], c[Nmax], tata[Nmax], v[Nmax];
vector<int> lv[Nmax];

void citire()
{
    scanf("%d\n", &n);
    for (i=1; i<=n; ++i)
        scanf("%d %d\n", &grin[i], &grout[i]);
}

int bf()
{
    int st = 0, dr = 1, nod, i;
    memset(tata, -1, sizeof(tata));
    memset(v, 0, sizeof(v));
    c[dr] = s;
    while (st < dr)
    {
        nod = c[++st];
        for (i=0; i<sz(lv[nod]); ++i)
            if (!v[lv[nod][i]] && cap[nod][lv[nod][i]] > 0)
            {
                v[lv[nod][i]] = 1;
                tata[lv[nod][i]] = nod;
                c[++dr] = lv[nod][i];
                if (lv[nod][i] == d)
                    return 1;
            }
    }
    return 0;
}

void solve()
{
    int nod;
    //construiesc graful
    
    s = 0;
    d = 2 * n + 1;
    
    for (i=1; i<=n; ++i)
    {
        cap[s][i] = grin[i];
        lv[s].pb(i);
        cap[n+i][d] = grout[i];
        lv[n+i].pb(d);
    }
    
    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j)
            if (i != j)
            {
                cap[i][n+j] = 1;
                lv[i].pb(n+j);
                lv[n+j].pb(i);
            }
    
    //fac flux
    
    while (bf())
    {
        for (i=n+1; i<=2*n; ++i)
            if (tata[i] != -1 && cap[i][d] > 0)
            {
                flux = cap[i][d];
                for (nod = i; nod != s; nod = tata[nod])
                    flux = min(flux, cap[tata[nod]][nod]);
                ct += flux;
                cap[i][d] -= flux;
                cap[d][i] += flux;
                for (nod = i; nod != s; nod = tata[nod])
                {
                    cap[tata[nod]][nod] -= flux;
                    cap[nod][tata[nod]] += flux;
                }
            }
    }
    printf("%d\n", ct);
    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j)
            if (i != j && !cap[i][n+j])
                printf("%d %d\n",i, j);
}

int main()
{
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);
    citire();
    solve();
    return 0;
}