Cod sursa(job #2961038)

Utilizator TeoDiDiaconescu Teodora TeoDi Data 5 ianuarie 2023 16:42:57
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <bits/stdc++.h>

using namespace std;

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

int MaxFlow(vector<vector<int>> &cap, int s, int t) {
    int n = cap.size();
    vector<vector<int>> flow(n, vector<int>(n));
    int ans = 0;
    while (true) {
        vector<int> par(n, -1);
        par[s] = -2;
        queue<int> q;
        q.push(s);
        while (!q.empty() && par[t] == -1) {
            int u = q.front();
            q.pop();
            for (int v = 0; v < n; v++) {
                if (par[v] == -1 && cap[u][v] - flow[u][v] > 0) {
                    par[v] = u;
                    q.push(v);
                }
            }
        }
        if (par[t] == -1) {
            break;
        }
        int f = INT_MAX;
        for (int v = t; v != s; v = par[v]) {
            f = min(f, cap[par[v]][v] - flow[par[v]][v]);
        }
        for (int v = t; v != s; v = par[v]) {
            flow[par[v]][v] += f;
            flow[v][par[v]] -= f;
        }
        ans += f;
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(flow[i][j] > 0 && i != 0 && j != n - 1) {
                fout << i << " " << j - (n/2) + 1 << "\n";
            }
        }
    }
    return ans;
}


int main() {
    int n, m1 = 0, m2 = 0;
    fin >> n ;
    int s = 0, t = 2 * n + 1;
    vector<vector<int>> cap(2*n+2, vector<int>(2 * n + 2, 0));
    for(int i = 1; i <= n;i++)
    {
        int x, y;
        fin >> x >> y;
        cap[s][i] = x;
        cap[i + n][t] = y;
        m1 += x;
        m2 += y;
    }
    if(m1 != m2)
    {
        fout << "Imposibil";
        return 0;
    }
    for(int i = 1; i <= n;i++)
    {
        for(int j = n + 1; j <= 2 * n;j++)
        {
            if(i != j - n)
            {
                cap[i][j] = 1;
            }
        }
    }
    fout<< m1 << "\n";
    MaxFlow(cap, s, t);
    return 0;
}