Cod sursa(job #2620805)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 29 mai 2020 18:12:02
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 205;

vector<int> graf[MAXN];
queue<int> coada;
int flux[MAXN][MAXN], sursa[MAXN];
bool viz[MAXN];

int n, s, d;

int main()
{
    ifstream fin("harta.in");
    ofstream fout("harta.out");
    fin >> n;
    s = 0; d = 2 * n + 1;
    for(int i = 1; i <= n; ++i){
        int out, in;
        fin >> out >> in;
        flux[s][i] = out; flux[i + n][d] = in;
        graf[s].push_back(i); graf[i].push_back(s);
        graf[i + n].push_back(d); graf[d].push_back(i + n);
    }
    for(int i = 1; i <= n; ++i){
        for(int j = n + 1; j <= 2 * n; ++j){
            if(i == j - n) continue;
            flux[i][j] = 1;
            graf[i].push_back(j); graf[j].push_back(i);
        }
    }
    bool sink = 1;
    while(sink){
        sink = 0;
        memset(viz, 0, 2 * n + 2);
        coada.push(s);
        while(!coada.empty()){
            int x = coada.front();
            coada.pop();
            for(auto y: graf[x]){
                if(!viz[y] && flux[x][y] > 0){
                    viz[y] = 1;
                    sursa[y] = x;
                    if(y == d) sink = 1;
                    else coada.push(y);
                }
            }
        }
        for(auto x: graf[d]){
            if(!viz[x] || flux[x][d] == 0) continue;
            int mnflux = 1e9;
            sursa[d] = x;
            for(int crt = d; crt > s; crt = sursa[crt]) mnflux = min(mnflux, flux[sursa[crt]][crt]);
            for(int crt = d; crt > s; crt = sursa[crt]){
                flux[sursa[crt]][crt] -= mnflux;
                flux[crt][sursa[crt]] += mnflux;
            }
        }
    }
    int m = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = n + 1; j <= 2 * n; ++j)
            if(i != j - n && flux[i][j] == 0) m++;
    }
    fout << m << "\n";
    for(int i = 1; i <= n; ++i){
        for(int j = n + 1; j <= 2 * n; ++j)
            if(i != j - n && flux[i][j] == 0) fout << i << " " << j - n << "\n";
    }
    return 0;
}