Cod sursa(job #1385837)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 12 martie 2015 14:38:07
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <fstream>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;

ifstream is("harta.in");
ofstream os("harta2.out");

int N, n, m;
vector<bool> ok;
vector<int> in, out, t;
vector<vector<int> > c, g, wr;

void Read();
void Build();
bool BFS();

int main()
{
    Read();
    Build();
    t = vector<int>(N + 1);
    wr = vector<vector<int> >(n + 1, vector<int>(n + 1, 0));
    int answ = 0, fmin;
    while ( BFS() && answ < m )
        for ( int nodv = n + 1; nodv < N; ++nodv )
            if ( ok[nodv] && c[nodv][N] > 0 )
            {
                t[N] = nodv;
               // if ( wr[t[t[N]]][t[N] - n] )
                //    continue;
                fmin = INF;
                for ( int i = N; i; i = t[i] )
                    fmin = min(fmin, c[t[i]][i]);
                if ( !fmin )
                    continue;
                wr[t[t[N]]][t[N] - n] = 1;
                for ( int i = N; i; i = t[i] )
                {
                    --c[t[i]][i];
                    ++c[i][t[i]];
                }
                ++answ;
            }
    os << m << "\n";
    for ( int i = 1; i <= n && m; ++i )
        for ( int j = 1; j <= n && m; ++j )
            if ( c[i + n][j] )
            {
                os << i << " " << j << "\n";
               // --m;
            }
    is.close();
    os.close();
    return 0;
}

bool BFS()
{
    ok = vector<bool>(N + 1, 0);
    queue<int> q;
    q.push(0);
    ok[0] = 1;
    int nod;
    while ( !q.empty() )
    {
        nod = q.front();
        q.pop();
        if ( nod == N )
            continue;
        for ( vector<int>::iterator nodv = g[nod].begin(); nodv != g[nod].end(); ++nodv )
            if ( !ok[*nodv] && c[nod][*nodv] > 0 )
            {
                ok[*nodv] = 1;
                t[*nodv] = nod;
                q.push(*nodv);
            }
    }
    return ok[N];
}

void Build()
{
    N = 2 * n + 1;
    c = vector<vector<int> >(N + 1, vector<int>(N + 1));
    g = vector<vector<int> >(N + 1);
    for ( int i = 1; i <= n; ++i )
    {
        c[0][i] = in[i];
        c[n + i][N] = out[i];
        g[n + i].push_back(N);
        g[0].push_back(i);
    }
    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= n; ++j )
            if ( i != j )
            {
                c[i][n + j] = 1;
                g[i].push_back(n + j);
                g[n + j].push_back(i);
            }
}

void Read()
{
    is >> n;
    in = out = vector<int>(n + 1);
    for ( int i = 1; i <= n; ++i )
    {
        is >> out[i] >> in[i];
        m += out[i];
    }
}