Cod sursa(job #2954467)

Utilizator T_george_TGeorge Teodorescu T_george_T Data 14 decembrie 2022 15:45:00
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <string.h>

using namespace std;

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

const int NMAX = 2*1e3 + 10;

int n, m, cap[NMAX][NMAX], seen[NMAX], f[NMAX][NMAX], father[NMAX];

vector<int> g[NMAX];

int bf() {
    queue<int> q;
    memset(seen, 0, sizeof(seen));

    q.push(0);
    seen[0] = 1;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        if (node == 2*n+1)
            continue;
        for (int next: g[node]) {
            if (cap[node][next] == f[node][next] || seen[next])
                continue;
            father[next]=node;
            seen[next] = 1;
            q.push(next);

        }
    }

    return seen[2*n+1];
}

int main() {

    in >> n;

    for (int i = 1, a, b; i <= n; i++) {
        in >> a >> b;
        g[0].push_back(i);
        g[i].push_back(0);
        cap[0][i]=a;

        g[n+i].push_back(2*n+1);
        g[2*n+1].push_back(n+i);
        cap[n+i][2*n+1]=b;
    }

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

    int flow = 0;
    while (bf())
        for (int node: g[2*n+1]) {
            int fmin = 2e9;

            if (f[node][2*n+1] == cap[node][2*n+1] || !seen[node])
                continue;
            father[2*n+1] = node;
            for (node = 2*n+1; node != 0; node = father[node]) {
                fmin = min(fmin, cap[father[node]][node] - f[father[node]][node]);
            }
            if (fmin == 0)
                continue;
            for (node = 2*n+1; node != 0; node = father[node]) {
                f[father[node]][node] += fmin;
                f[node][father[node]] -= fmin;
            }
            flow += fmin;
        }

    out << flow<<'\n';

    for(int i=1;i<=n;i++)
        for(int j=n+1;j<=2*n;j++)
            if(i+n!=j && f[i][j]==1)
                out<<i<<" "<<j-n<<'\n';


    return 0;
}