Cod sursa(job #1538138)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 28 noiembrie 2015 16:04:22
Problema Taramul Nicaieri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define INF 0x3f3f3f3f
using namespace std;

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

using VI = vector<int>;
using VVI = vector<VI>;

int n, m;
VI in, out, t;
VVI g, c;
bitset<205> ok;

void Read();
void Build();
bool Bfs();

int main()
{
    Read();
    Build();
    t = VI(2 * n + 2);
    int fmin, answ = 0;
    while ( Bfs() && answ < m )
        for ( int nodv = n + 1; nodv <= 2 * n; ++nodv )
        {
            if ( !ok[nodv] || c[nodv][2 * n + 1] < 0 )
                continue;
            fmin = INF;
            t[2 * n + 1] = nodv;
            for ( int x = 2 * n + 1; x; x = t[x] )
                fmin = min(fmin, c[t[x]][x]);
            if ( !fmin )
                continue;
            for ( int x = 2 * n + 1; x; x = t[x] )
            {
                --c[t[x]][x];
                ++c[x][t[x]];
            }
            ++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 << j << " " << i << "\n";
                --m;
            }
    is.close();
    os.close();
    return 0;
}

bool Bfs()
{
    ok.reset();
    queue<int> q;
    q.push(0);
    int nod;
    while ( !q.empty() )
    {
        nod = q.front();
        q.pop();
        if ( nod == n + 1 )
            continue;
        for ( const auto &nodv : g[nod] )
            if ( !ok[nodv] && c[nod][nodv] > 0 )
            {
                ok[nodv] = 1;
                q.push(nodv);
                t[nodv] = nod;
            }
    }
    return ok[n + 1];
}

void Build()
{
    g = VVI(2 * n + 2);
    c = VVI(2 * n + 2, VI(2 * n + 2));
    for ( int i = 1; i <= n; ++i )
    {
        g[0].push_back(i);
        g[n + i].push_back(2 * n + 1);
        c[0][i] = in[i];
        c[n + i][2 * n + 1] = out[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 = VI(n + 1);
    for ( int i = 1; i <= n; ++i )
    {
        is >> in[i] >> out[i];
        m += in[i];
    }
}