Cod sursa(job #2956619)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 19 decembrie 2022 21:42:17
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
const int maxn = 305;
int intrare[maxn];
int iesire[maxn];
int dist[maxn];

struct muchie {
    int nod, vec, flux, cap;
};

vector <muchie> v[maxn]; /// graful generat sa bag flux pe el
muchie tata[maxn];
queue <int> q;
vector <muchie> drum;
int n;
int sursa, destinatie;

bool bfs()
{
    for(int i = 1; i <= n * 2 + 2; i++)
    {
        dist[i] = (1 << 30);
        tata[i] = {0, 0, 0};
    }
    dist[sursa] = 0;
    q.push(sursa);
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        for(auto it : v[nod])
        {
            if(dist[it.vec] > dist[nod] + 1 && it.flux < it.cap) /// pot trimite flux pe aici
            {
                dist[it.vec] = dist[nod] + 1;
                tata[it.vec] = it;
                q.push(it.vec);
            }
        }
    }
    if(dist[destinatie] != (1 << 30))
        return 1;
    return 0;
}

int main()
{
    in >> n;
    /// pun 1...n nodurile de pe partea stanga
    /// pun n+1, n+2, ..., 2n  nodurile de pe partea dreapta
    /// 2n+1 - sursa, 2n+2 - destinatie
    sursa = 2 * n + 1;
    destinatie = 2 * n + 2;
    int sol = 0;
    for(int i = 1; i <= n; i++)
    {
        in >> iesire[i] >> intrare[i];
        /// trag liniile   0->i,   (n+i) -> 2n+1
        v[sursa].push_back({sursa, i, 0, iesire[i]});
        v[i].push_back({i, sursa, 0, 0});
        v[n + i].push_back({n + i, destinatie, 0, intrare[i]});
        v[destinatie].push_back({destinatie, n + i, 0, 0});
        sol = sol + iesire[i];
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = n + 1; j <= 2 * n; j++)
        {
            if(i + n != j)  /// trag muchiile (x, y) de capacitate 1 unde x, y nu reprezita acelasi lucru
            {
                v[i].push_back({i, j, 0, 1});
                v[j].push_back({j, i, 0, 0});
            }
        }
    }
    /*
    for(int i = 1; i <= 2 * n + 2; i++)
        for(auto it : v[i])
            cerr << i << " " << it.vec << " " << it.cap << "\n";
    */
    /// acum dau copy paste la flux
    while(bfs()) /// cat timp gasesc un drum de la 1 la n
    {
        int act = destinatie;
        drum.clear();
        while(tata[act].nod != 0)
        {
            drum.push_back(tata[act]);
            act = tata[act].nod;
        }
        int posibil = (1 << 30); /// fluxul maxim pe care il pot trimite pe drumul gasit
        for(auto it : drum) /// calculez ce flux pot trimite
            posibil = min(posibil, it.cap - it.flux);
        for(auto m : drum) /// scad si adun fluxul pe care il bag din toate muchiile
        {
            int x = m.nod;
            int y = m.vec;
            for(int i = 0; i < v[x].size(); i++) /// gasesc muchia (x, y) si adun fluxul bagat
            {
                if(v[x][i].vec == y)
                {
                    v[x][i].flux += posibil;
                    break;
                }
            }
            for(int i = 0; i < v[y].size(); i++)
            {
                if(v[y][i].vec == x)
                {
                    v[y][i].flux -= posibil; /// gasesc muchia (y, x) si scad fluxul bagat
                    break;
                }
            }
        }
    }
    out << sol << "\n";
    for(int i = 1; i <= n; i++)
        for(auto it : v[i])
            if(it.flux > 0)
                out << it.nod << " " << it.vec - n << "\n";
    return 0;
}