Pagini recente » Cod sursa (job #1224066) | Cod sursa (job #402452) | Cod sursa (job #1693540) | Cod sursa (job #2952352) | Cod sursa (job #3189940)
#include <bits/stdc++.h>
using namespace std;
//pb6:https://www.infoarena.ro/problema/harta
ifstream fin("harta.in");
ofstream fout("harta.out");
class Graf {
public:
int nr_noduri;
vector<vector<int>> lista_vecini;
vector<vector<int>> capacitati;
vector<vector<int>> flux;
Graf(int n) : nr_noduri(n){
capacitati.resize(nr_noduri, vector<int>(n, 0));
flux.resize(nr_noduri, vector<int>(n, 0));
lista_vecini.resize(nr_noduri);
}
void adauga_capacitate(int x, int y, int capacitate) {
lista_vecini[x].push_back(y);
lista_vecini[y].push_back(x);
capacitati[x][y] = capacitate;
}
bool BFS(vector<int>& tati) {
queue<int> coada;
vector<int> vizitati(nr_noduri, 0);
int sursa = nr_noduri ;
int destinatie = nr_noduri ;
coada.push(sursa);
vizitati[sursa] = 1;
while (!coada.empty()) {
int nod = coada.front();
coada.pop();
for (size_t i = 0; i < lista_vecini[nod].size(); i++) {
int vecin = lista_vecini[nod][i];
if (vizitati[vecin] == 0 && (capacitati[nod][vecin] - flux[nod][vecin] > 0)) {
coada.push(vecin);
tati[vecin] = nod;
vizitati[vecin] = 1;
}
}
}
return vizitati[destinatie];
}
int fluxMaxim() {
int fluxMaxim = 0;
int destinatie = nr_noduri - 1;
int sursa = nr_noduri - 2;
vector<int> tati(nr_noduri, -1);
while (BFS(tati)) {
int capacitateMinima = static_cast<int>(1e18);
int nod = destinatie;
while (nod != sursa) {
capacitateMinima = min(capacitati[tati[nod]][nod] - flux[tati[nod]][nod], capacitateMinima);
nod = tati[nod];
}
fluxMaxim += capacitateMinima;
nod = destinatie;
while (nod != sursa) {
flux[tati[nod]][nod] += capacitateMinima;
flux[nod][tati[nod]] -= capacitateMinima;
nod = tati[nod];
}
for (int i = 0; i < nr_noduri; i++) {
tati[i] = -1;
}
}
return fluxMaxim;
}
};
int main() {
int N, x, y;
fin >> N;
Graf g(2 * N + 2);
for (int i = 0; i < N; i++) {
fin >> x >> y;
g.adauga_capacitate(2 * N, i, x);
g.adauga_capacitate(i + N, 2 * N + 1, y);
for (int j = 0; j < N; j++) {
if (i != j)
g.adauga_capacitate(i, j + N, 1);
}
}
fin.close();
fout << g.fluxMaxim() << '\n';
vector<vector<int>> rez = g.flux;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (rez[i][j + N] == 1)
fout << i + 1 << ' ' << j + 1 << '\n';
}
}
fout.close();
return 0;
}