Pagini recente » Cod sursa (job #1631450) | Cod sursa (job #2255793) | Cod sursa (job #2635042) | Cod sursa (job #253942) | Cod sursa (job #3190034)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 205; // Numărul maxim de noduri (N orașe + N intermediare + sursă + destinație)
const int INF = 1e9; // Valoarea infinitului pentru acest context
int N, capacitate[MAXN][MAXN], flux[MAXN][MAXN], parinte[MAXN];
vector<int> graf[MAXN];
bool bfs(int s, int t) {
memset(parinte, -1, sizeof(parinte));
queue<int> q;
q.push(s);
parinte[s] = -2;
while (!q.empty()) {
int nod = q.front();
q.pop();
for (int vecin : graf[nod]) {
if (parinte[vecin] == -1 && capacitate[nod][vecin] - flux[nod][vecin] > 0) {
parinte[vecin] = nod;
if (vecin == t) {
return true;
}
q.push(vecin);
}
}
}
return false;
}
int fordFulkerson(int s, int t) {
int flux_maxim = 0;
while (bfs(s, t)) {
int flux_curent = INF;
for (int nod = t; nod != s; nod = parinte[nod]) {
int prev = parinte[nod];
flux_curent = min(flux_curent, capacitate[prev][nod] - flux[prev][nod]);
}
for (int nod = t; nod != s; nod = parinte[nod]) {
int prev = parinte[nod];
flux[prev][nod] += flux_curent;
flux[nod][prev] -= flux_curent;
}
flux_maxim += flux_curent;
}
return flux_maxim;
}
int main() {
ifstream fin("harta.in");
ofstream fout("harta.out");
fin >> N;
int s = 0, t = 2 * N + 1; // Sursa și destinația în graf
for (int i = 1, a, b; i <= N; ++i) {
fin >> a >> b;
graf[s].push_back(i);
graf[i].push_back(s);
capacitate[s][i] = a;
graf[i + N].push_back(t);
graf[t].push_back(i + N);
capacitate[i + N][t] = b;
for (int j = 1; j <= N; ++j) {
graf[i].push_back(j + N);
graf[j + N].push_back(i);
capacitate[i][j + N] = 1;
}
}
int flux_maxim = fordFulkerson(s, t);
fout << flux_maxim << "\n";
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
if (flux[i][j + N] > 0) {
fout << i << " " << j << "\n";
}
}
}
fin.close();
fout.close();
return 0;
}