Cod sursa(job #2957455)

Utilizator ralucarRogoza Raluca ralucar Data 22 decembrie 2022 17:15:25
Problema Taramul Nicaieri Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define max_capacity 1e9
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");

int n, max_flow;
int capacity[202][202];
vector<int>parent, visited;
vector<int>adjacency_list[101];
queue<int>q;

int bfs(){
    visited.assign(2*n+2, 0);
    parent.assign(2*n+2, 0);
    while(!q.empty()){
        q.pop();
    }
    q.push(0);
    visited[0]=1;
    parent[0]=0;
    while(!q.empty()){
        int node=q.front();
        q.pop();
        for(auto neighbour:adjacency_list[node]){
            if(visited[neighbour]==0 && capacity[node][neighbour]>0) {
                q.push(neighbour);
                parent[neighbour]=node;
                visited[neighbour]=1;
                if(neighbour == 2*n+1) return 1;
            }
        }
    }
    return visited[2*n+1];
}
int main() {
    int x, y, z;
    fin>>n;
    for(int i=1; i<=n; i++){
        fin>>x>>y;
        z = n;
        adjacency_list[0].push_back(i);
        adjacency_list[i].push_back(0);
        adjacency_list[2*n+1].push_back(n+i);
        adjacency_list[n+i].push_back(2*n+1);
        capacity[0][i]=x;
        capacity[n+i][2*n+1]=y;
    }
    for(int i=1; i<=n; i++){
        for(int j=n+1; j<=2*n; j++){
            if(j != n+i){
                adjacency_list[i].push_back(j);
                adjacency_list[j].push_back(i);
                capacity[i][j]=1;
            }
        }
    }
    while(bfs()) {
        for (auto node: adjacency_list[2*n+1]) {
            if (!visited[node])
                continue;
            parent[2*n+1] = node;
            int flow = max_capacity;
            for (node = 2*n+1; node != 0; node = parent[node]) {
                flow = min(flow, capacity[parent[node]][node]);
            }
            if (flow == 0) continue;
            for (node = 2*n+1; node != 0; node = parent[node]) {
                capacity[parent[node]][node] -= flow;
                capacity[node][parent[node]] += flow;
            }
            max_flow += flow;
        }
    }
    fout<<max_flow<<'\n';
    for(int i=1; i<=n; i++){
        for(int j=n+1; j<=2*n+1; j++){
            if(capacity[i][j] == 0 && capacity[j][i] == 1){
                fout<<i<<" "<<j-n<<'\n';
            }
        }
    }
    fin.close();
    fout.close();
    return 0;
}