Cod sursa(job #2962358)

Utilizator maria10Cioclov Maria maria10 Data 8 ianuarie 2023 13:53:11
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#pragma GCC optimize "O3"
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");

queue<int> bfs;
vector<vector<int>> lista;
int cap[205][205];

int main(){
    int n, t, x, y;
    fin>>n;
    t = 2 * n + 2;
    lista.resize(t);

    for(int i=1; i<=n; i++){
        fin>>x>>y;
        lista[0].push_back(i);
        lista[i].push_back(0);
        cap[0][i] = x;
        lista[i+n].push_back(t-1);
        lista[t-1].push_back(i+n);
        cap[i+n][t-1] = y;
    }

    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i!=j){
                lista[i].push_back(n+j);
                cap[i][n+j] = 1;
                lista[n+j].push_back(i);
            }



    int b, p, F=0;

    while(true){
        int parent[t];
        for(int i=0; i<t; i++) parent[i] = -2;

        bfs.push(0);
        parent[0] = -1;

        while(!bfs.empty()){
            x = bfs.front();
            bfs.pop();

            for(auto y: lista[x])
                if(parent[y] == -2  && cap[x][y]) {
                    parent[y] = x;
                    if(y == t-1) break;
                    bfs.push(y);

                }

            if(parent[t-1] != -2) break;
        }

        p = parent[t-1];
        if(p != -2) {
            b = 111;
            x = t-1;
            while (p != -1) {
                if(cap[p][x] < b) b = cap[p][x];
                x = p;
                p = parent[p];
            }


            F += b;
            x = t-1;
            p = parent[x];
            while (p != -1){
                cap[p][x] -= b;
                cap[x][p] += b;
                x = p;
                p = parent[p];
            }

            while(!bfs.empty()) bfs.pop();
        }
        else break;
    }

    fout<<F<<'\n';
    for(int i=1; i<=n; i++)
        for(auto j: lista[i])
            if(j && !cap[i][j]) fout<<i<<" "<<j-n<<'\n';

}