Cod sursa(job #2691887)

Utilizator DiagrDiana Grigore Diagr Data 30 decembrie 2020 16:02:24
Problema Taramul Nicaieri Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <iostream>
#include <bits/stdc++.h>
#define maxim  1e9 + 2
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n, dp[2001], dm[2001], graf[5001][5001], graf_rezidual[5001][5001], s, t, vizitat[5001], tata[5001], flux_maxim, suma_g;
set<pair<int,int>> muchii;
vector<pair<int,int>> stuff[2001];
int bfs()
{
    queue<int> q;
    tata[s] = -1;
    q.push(s);

    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = 0; i <= 2 * n + 1; i++)
            if(!vizitat[i] && graf_rezidual[u][i] > 0)
            {
                q.push(i);
                tata[i] = u;
                vizitat[i] = 1;
            }
    }
    return vizitat[t];
}

int FordFulkerson()
{
    for(int i = 0; i <= 2 * n + 1; i++)
        for(int j = 0; j <= 2 * n + 1; j++)
            graf_rezidual[i][j] = graf[i][j];
    flux_maxim = 0;
    while(bfs())
    {
        for(int i = 0; i <= 2 * n + 1; i++)
            vizitat[i] = 0;
        int flux_curent = maxim;
        int current = t;
        while (current != s)
        {
            flux_curent = min(flux_curent, graf_rezidual[tata[current]][current]);
            current = tata[current];
        }
        current = t;
        while(current != s)
        {
            graf_rezidual[current][tata[current]] += flux_curent;
            graf_rezidual[tata[current]][current] -= flux_curent;
            current = tata[current];
        }
        flux_maxim += flux_curent;
    }

    return flux_maxim;
}

int main() {
    f >> n;
    for(int i = 1; i <= n; i++)
    {
        f >> dp[i] >> dm[i];                     //citim gradele de iesire (cu plus)
        suma_g = dp[i];
    }
    s = 0; t = 2 * n + 1;           //adaugam vf. de start si de final
    for(int i = 1; i <= n; i++)
        for(int j = n + 1; j <= 2 * n; j++)     //contruim reteaua de transport (de la n+1 la 2*n cealalta parte a bipartitiei)
            if(i != j - n)
            {
                graf[i][j] = 1;
                stuff[i].emplace_back(j,1);
            }
    for(int i = 1; i <= n; i++)
    {
        graf[s][i] = dp[i]; //adaugam arce iesire
        graf[n + i][t] = dm[i]; //adaugam arce intrare
    }
    flux_maxim = FordFulkerson(); //gasim fluxul maxim in retea
    g << flux_maxim << '\n';
    if(suma_g <= flux_maxim) //stabilim daca graful poate fi construit
    {
        for(int i = 1; i <= n; i++)
            for(auto x : stuff[i])
                if(x.second - graf_rezidual[i][x.first] != 0)   //arcele cu flux pozitiv sunt arce in G
                    g << i << " " << x.first - n << '\n';
    }


    return 0;
}