Cod sursa(job #2961611)

Utilizator NefelibataAnton Marius Alexandru Nefelibata Data 6 ianuarie 2023 19:12:11
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

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

int n, s, d, mmm;
int cap[201][201], flux[201][201], p[201];
vector <int> G[201];
vector <pair <int, int>> ans;
bool path[201];

bool bfs() {
    memset(path, 0, sizeof path);
    queue <int> q;
    q.push(s);
    while(!q.empty()) {
        int poz = q.front();
        q.pop();
        if(poz == d) continue;
        for(auto vecin : G[poz]) {
            if(!path[vecin] && cap[poz][vecin] > flux[poz][vecin]) {
                path[vecin] = 1;
                p[vecin] = poz;
                q.push(vecin);
            }
        }
    }
    return path[d];
}


int main() {
    f>>n;
    s = 0;
    d = 2 * n + 1;
    for(int i = 1; i <= n; i++) {
        int x, y;
        f>>x>>y;
        cap[s][i] = x;
        cap[n + i][d] = y;
    }
    for(int i = 1; i <= n; i++) {
        G[s].push_back(i);
        G[i].push_back(s);
        G[d].push_back(n + i);
        G[n + i].push_back(d);
        for(int j = 1; j <= n; j++) {
            if(j != i) {
                G[i].push_back(j + n);
                G[j + n].push_back(i);
                cap[i][j + n] = 1;
            }
        }
    }
    while(bfs()) {
        for(int x = d; x != s; x = p[x]) {
            flux[p[x]][x]++;
            flux[x][p[x]]--;
        }
        mmm++;
    }
    o<<mmm<<'\n';
    for(int i = 1; i <= n; i++) for(int j = n + 1; j <= 2 * n; j++) if(flux[i][j]) o<<i<<' '<<j - n<<'\n';
    return 0;
}