Cod sursa(job #3188146)

Utilizator bestman4111Tiberiu Niculae bestman4111 Data 1 ianuarie 2024 22:28:49
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.99 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

#define INF 999999

int N, source, target, maxFlow;
vector<vector<int>> adi, capacity, flow;
vector<int> parinte, degreeIn, degreeOut;

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

int bfs(){
    queue<pair<int, int>> q;
    q.push({source, INF});
    while(!q.empty()){
        int node = q.front().first;
        int newFlow = q.front().second;
        q.pop();
        for(int i : adi[node]){
            if(parinte[i] == -1 && capacity[node][i] > 0){
                parinte[i] = node;
                newFlow = min(newFlow, capacity[node][i]);
                if(i == target){
                    return newFlow;
                }
                q.push({i, newFlow});
            }
        }
    }
    return 0;
}

int main()
{
    fin >> N;
    adi.resize(2 * N + 2);
    capacity.resize(2 * N + 2, vector<int>(2 * N + 2, 0));
    flow.resize(N + 1);
    parinte.resize(2 * N + 2, -1);
    degreeIn.resize(N + 1, 0);
    degreeOut.resize(N + 1, 0);
    for(int i = 1; i <= N; i++){
        fin >> degreeOut[i] >> degreeIn[i];
    }

    source = 0;
    target = 2 * N + 1;

    for(int i = 1; i <= N; i++){
        adi[source].push_back(i);
        adi[i].push_back(source);
        capacity[source][i] = degreeOut[i];
    }
    for(int i = N + 1; i < target; i++){
        adi[target].push_back(i);
        adi[i].push_back(target);
        capacity[i][target] = degreeIn[i - N];
    }
    for(int i = 1; i <= N; i++){
        for(int j = N + 1; j < target; j++){
            if(i + N == j){
                continue;
            }
            adi[i].push_back(j);
            adi[j].push_back(i);
            capacity[i][j] = 1;
        }
    }

    for(int i = 0; i <= target; i++){
        parinte[i] = -1;
    }
    parinte[source] = -2;

    int c;
    while(c = bfs()){
        maxFlow = maxFlow + c;
        int node = target;
        while(node != source){
            int stramos = parinte[node];
            capacity[stramos][node] -= c;
            capacity[node][stramos] += c;
            if(node > source && node < target && stramos > source && stramos < target){
                if(stramos < node){
                    flow[stramos].push_back(node);
                }
                else{
                    for(int i = 0; i < flow[node].size(); i++){
                        if(flow[node][i] == stramos){
                            flow[node].erase(flow[node].begin() + i);
                            break;
                        }
                    }
                }
            }
            node = stramos;
        }
        for(int i = 0; i <= target; i++){
            parinte[i] = -1;
        }
        parinte[source] = -2;
    }

    fout << maxFlow << "\n";
    for(int i = 1; i <= N; i++){
        for(int j : flow[i]){
            fout << i << " " << j - N << "\n";
        }
    }
    return 0;
}