Cod sursa(job #2480308)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 25 octombrie 2019 11:43:46
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 307;

int cap[DIM][DIM];
int in[DIM];
int out[DIM];

int dist[DIM];

pair <int, int> v[DIM];

vector <pair <int, int> > res;
vector <int> retea[DIM];

int from[DIM];

int S, D;

int n;

bitset <DIM> vis;

bool bfs()
{
    vis.reset();
    queue <int> q;

    vis[S] = true;
    q.push(S);

    while(!q.empty())
    {
        int nod = q.front();
        q.pop();

        for(auto i : retea[nod])
            if(vis[i] == false && cap[nod][i] > 0)
            {
                vis[i] = true;
                from[i] = nod;

                if(i != D)
                {
                    q.push(i);
                }
            }
    }

    if(vis[D] == true)
    {
        return true;
    }

    return false;
}

void muchie(int x, int y, int val)
{
    retea[x].push_back(y);
    retea[y].push_back(x);

    cap[x][y] += val;
}

main()
{
    fin >> n;

    for(int i = 1; i <= n; i++)
    {
        fin >> v[i].first;
        fin >> v[i].second;
    }

    S = 0;
    D = 2 * n + 1;

    for(int i = 1; i <= n; i++)
    {
        if(v[i].first)
            muchie(S, i, v[i].first);

        if(v[i].first)
            for(int j = 1; j <= n; j++)
                if(i != j)
                {
                    if(v[j].second)
                        muchie(i, j + n, 1);
                }

        if(v[i].second)
            muchie(i + n, D, v[i].second);
    }

    while(bfs())
    {
        for(int i = D; i != S; i = from[i])
        {
            cap[from[i]][i]--;
            cap[i][from[i]]++;
        }
    }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(cap[i + n][j])
                res.push_back({j, i});

    fout << res.size() << '\n';

    for(auto i : res)
    {
        fout << i.first << ' ' << i.second << '\n';
    }
}