Cod sursa(job #2835189)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 18 ianuarie 2022 10:59:55
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

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

int n, s, d, max_flux;
int cap[205][205], flux[205][205], p[205];
vector <int> G[205];
vector <pair <int, int>> ans;
bool traseu[205];

bool bfs()
{
    memset(traseu, 0, sizeof traseu);
    queue <int> q;
    q.push(s);
    while(!q.empty())
    {
        int poz = q.front();
        q.pop();
        if(poz == d)
            continue;
        for(auto vecin : G[poz])
        {
            if(!traseu[vecin] && cap[poz][vecin] > flux[poz][vecin])
            {
                traseu[vecin] = 1;
                p[vecin] = poz;
                q.push(vecin);
            }
        }
    }
    return traseu[d];
}


int main()
{
    fin >> n;
    s = 0;
    d = 2 * n + 1;
    for(int i = 1; i <= n; i++)
    {
        int a, b;
        fin >> a >> b;
        cap[s][i] = a;
        cap[n + i][d] = b;
    }
    for(int i = 1; i <= n; i++)
    {
        G[s].push_back(i);
        G[i].push_back(s);
        G[d].push_back(n + i);
        G[n + i].push_back(d);
        for(int j = 1; j <= n; j++)
        {
            if(j != i)
            {
                G[i].push_back(j + n);
                G[j + n].push_back(i);
                cap[i][j + n] = 1;
            }
        }
    }
    while(bfs())
    {
        for(int x = d; x != s; x = p[x])
        {
            flux[p[x]][x]++;
            flux[x][p[x]]--;
        }
        max_flux++;
    }
    fout << max_flux << '\n';
    for(int i = 1; i <= n; i++)
        for(int j = n + 1; j <= 2 * n; j++)
            if(flux[i][j])
                fout << i << ' ' << j - n << '\n';
    return 0;
}