Cod sursa(job #761826)

Utilizator Theorytheo .c Theory Data 27 iunie 2012 15:32:17
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include<fstream>
#include<queue>
#include<vector>

#define pb push_back
#define foreach(V) for(vector<int>::iterator it = G[V].begin(); it != G[V].end(); it++)
#define nmax 206

using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

int C[nmax][nmax], F[nmax][nmax], TT[nmax];
int N, S, x, y, D, sum;
bool use[nmax];
vector<int> G[nmax];

bool BFS()
{
    for(int i = 1; i <= D; i++, use[i] = false, TT[i] = -1);

    queue<int> q;
    use[S] = true;
    q.push(S);
    TT[S] = -1;

    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        foreach(x)
        {
            int nod =*it;
            if(C[x][nod] - F[x][nod] > 0 && use[nod] ==false)
            {
                use[nod] = true;
                q.push(nod);
                TT[nod] = x;
            }
        }

    }
    return use[D];
}
void solve()
{
    while( BFS())
        foreach(D)
        {

            int vmin = 1<<30, nod = *it;
            if(use[nod] && C[nod][D] - F[nod][D] > 0 )
            {

                for(int i = nod; i != S; i = TT[i] )
                    vmin = min(vmin, C[TT[i]][i] - F[TT[i]][i]);

                for(int i = nod; i != S; i = TT[i] )
                    F[TT[i]][i] += vmin,
                    F[i][TT[i]] -= vmin;
            }
        }



}

void read()
{
    fin >> N;
    D = 2 * N + 1;
    S = 0;
    for(int i = 1; i <= N; i++)
    {
        fin >>x >>y;
        G[0].pb(i);
        G[i].pb(0);
        G[i + N].pb(D);
        G[D].pb(i+N);
        C[S][i] = x;
        C[i + N][D] = y;
        sum += x;

    }

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N ;j++)
        if(i!=j){
            G[i].pb(j + N),
            G[j + N].pb(i),
            C[i][j+ N] = 1;
        }

}
int main()
{
    read();
    solve();
    fout << sum <<'\n';
    for(int i = 1; i <= N ;i++)
        for(int j = 1; j <= N ;j++)
            if(i != j && F[i][j + N])
                fout<< i << " " << j <<'\n' ;
    fin.close();
    return 0;
}