Cod sursa(job #2955710)

Utilizator RobertuRobert Udrea Robertu Data 17 decembrie 2022 17:35:28
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <bits/stdc++.h>
#define dim 220
#define inf INT_MAX
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");

/*
    Idee: Adaugam un nou start si un nou final(cu muchii de capacitati egale cu gradele out, respectiv in),
    si dublam nodurile, ca sa l putem lega pe fiecare cu fiecare, ca in curs, cu muchii de capacitate 1.
    De aici rulam algo de flux. Fluxul maxim obtinut ne da numarul de muchii adaugate, pentru ca fiecare
    are capacitate 1. Muchiile selectate sunt cele saturate, aka au ramas capacitate 0. 
*/

int tata[dim], a[dim][dim], in[dim], out[dim], n, m,  nod, flow, maxFlow;
bool viz[dim];

bool bfs() {
    queue<int> coada;
    memset(tata, 0, sizeof(tata));
    memset(viz, false, sizeof(viz));

    coada.push(0);
    viz[0] = true;
    tata[0] = -1;
    while(!coada.empty()) {
        int front = coada.front();
        coada.pop();

        if(front == 2*n + 1) {
            return true;
        }

        for(int i = 1; i <= 2*n + 1; i++) {
            if( !viz[i] &&  a[front][i] > 0) {
                coada.push(i);
                viz[i] = true;
                tata[i] = front;
            }
        }
    }
    return false;
}

int main() {
    fin >> n;
    for(int i = 1; i <= n; i++) {   
        fin >> out[i] >> in[i];
        a[0][i] = out[i];
        a[n + i][2*n + 1] = in[i];

        for(int j = 1; j <= n; j++) 
            if(j != i) 
                a[i][n + j] = 1;
    }

    while(bfs()) {
        for(int i = 1; i <= n; i++) {
            if( viz[n + i] && a[n + i][2*n + 1] > 0 ) {
                flow = inf;
                tata[2*n + 1] = n + i;
                for(nod = 2*n + 1; nod != 0; nod = tata[nod]) {
                    flow = min(flow, a[ tata[nod] ][nod]);
                }

                if(flow == 0) continue;

                for(nod = 2*n + 1; nod != 0; nod = tata[nod]) {
                    a[ tata[nod] ][nod] -= flow;
                    a[nod][ tata[nod] ] += flow;
                }
                maxFlow += flow;
            }
        }
    }

    fout << maxFlow << '\n';
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++)
            if( a[i][n + j] == 0 && i != j)
                fout << i << " " << j << '\n';
        
    }
       
    return 0;
}