Cod sursa(job #886528)

Utilizator ericptsStavarache Petru Eric ericpts Data 22 februarie 2013 22:50:10
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
#define pb push_back
#define maxn 250
#define forEach(G) for( typeof(G.begin()) it = G.begin() ; it != G.end() ; ++ it)
ifstream in("harta.in");
ofstream out("harta.out");

vector<int> graf[maxn];

int Q[maxn];
int TT[maxn];
int F[maxn][maxn];
int C[maxn][maxn];
bool viz[maxn];
int n;
int start,end;

bool BFS()
{

    int i,nod;
    memset(TT,0,sizeof(TT));
    memset(viz,0,sizeof(viz));
    Q[0]=1;
    Q[1]=start;
    TT[start]=-1;
    viz[start]=1;
    for(i=1;i<=Q[0];++i)
    {
        nod = Q[i];

        if(nod == end)
            continue;

        forEach(graf[nod])
        {
            if(viz[*it] || C[nod][*it] ==  F[nod][*it])
                continue;
            TT[*it] = nod;
            viz[*it]=1;
            Q[++Q[0]]=*it;
        }
    }

    return TT[end];
}

void chk()
{
    int nod;
    bool good;
    good = 1;
    for(nod = end; nod != start; nod = TT[nod])
        if(F[TT[nod]][nod]== C[TT[nod]][nod])
        {
            good = 0;
            return;
        }

    if(!good)
        return ;
    for(nod = end;nod != start; nod = TT[nod])
    {
        F[TT[nod]][nod]++;
        F[nod][TT[nod]]--;
    }
}

void aug()
{

    forEach(graf[end])
    {

        if(!TT[*it] || F[*it][end] == C[*it][end])
            continue;
        TT[end] = *it;
        chk();
    }
}

int main()
{
    int i,inc,outg,j;
    in >> n;
    start = 0;
    int show=0;
    end = 2*n+1;
    for(i=1;i<=n;++i)
    {
        in >> outg >> inc;
        show += outg;
        graf[start].pb(i);
        graf[i].pb(start);
        graf[i+n].pb(end);
        graf[end].pb(i+n);
        C[start][i] = outg;
        C[i+n][end] = inc;
    }
    for(i=1;i<=n;++i)
        for(j=n+1;j<=2*n;++j)
            if(i != j-n)
            {
                graf[i].pb(j);
                graf[j].pb(i);
                C[i][j] = 1;
            }
    out << show << "\n";
    for(;BFS();aug());
    for(i=1;i<=n;++i)
        for(j=n+1;j<=2*n;++j)
            if(F[i][j]==1)
                out << i << " " << j-n << "\n";
}