Pagini recente » Cod sursa (job #731477) | Cod sursa (job #1395039) | Cod sursa (job #1014101) | Cod sursa (job #1056204) | Cod sursa (job #3189974)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
// initializam un flux null si o matrice de capacitati
int cap[1001][1001], flux[1001][1001];
// initializam un vector de parinti
vector<int> parent;
// initializam o matrice de adiacenta
vector<int> mat[1001];
// numarul de orase
int n;
// bfs pentru a gasi un drum de crestere (un lant de la sursa la destinatie)
// capacele muchiilor trebuie sa fie strict pozitive, si mai mari decat fluxul curent
int bfs(int start, int last) {
// initializam o coada si un vector de vizitati
deque<int> q;
vector<bool> visited(last + 1, false);
// initializam vectorul de parinti
parent.assign(last + 1, 0);
q.push_back(start);
visited[start] = true;
while (!q.empty()) {
int nod = q.front();
q.pop_front();
// daca am ajuns la destinatie, iesim din bfs
if (nod == last) break;
// parcurgem vecinii nodului curent
for (int i = 0; i < mat[nod].size(); i++) {
int vecin = mat[nod][i];
// daca capacitatea muchiei este mai mare decat fluxul curent
// adaugam nodul in coada
if (!visited[vecin] && cap[nod][vecin] > flux[nod][vecin]) {
q.push_back(vecin);
// tinem nodul anterior in vectorul de parinti
// pentru a reconstrui drumul de crestere ulterior
parent[vecin] = nod;
visited[vecin] = true;
}
}
}
// daca am ajuns la destinatie(am gasit un drum de crestere), returnam 1
// altfel, returnam 0
if (parent[last]) return 1;
return 0;
}
// algoritmul lui Edmonds-Karp - determinam fluxul maxim
int edmonds_karp(int start, int last) {
int flow = 0;
int i, mini;
// cat timp exista un drum de crestere (aflate cu bfs)
while (bfs(start, last)) {
mini = INT_MAX;
i = last;
// determinam fluxul minim pe drumul de crestere,
// comparand fluxul dintre nodul curent si parintele sau cu fluxul minim curent
while (i != 0) {
if ((cap[parent[i]][i] - flux[parent[i]][i]) < mini)
mini = (cap[parent[i]][i] - flux[parent[i]][i]);
i = parent[i];
}
i = last;
// actualizam fluxurile pe drum
while (i != 0) {
// fluxul creste pe muchiile directe si scade pe cele inverse
flux[parent[i]][i] += mini;
flux[i][parent[i]] -= mini;
i = parent[i];
}
// adaugam fluxul minim la fluxul total
flow += mini;
}
return flow;
}
int main() {
int start, last, x, y;
fin >> n;
start = 0;
last = n + n + 1;
// initializam matricea de adiacenta si matricea de capacitati
for (int i = 1; i <= n; i++) {
fin >> x >> y;
int j = n + i;
mat[start].push_back(i);
mat[i].push_back(start);
cap[start][i] = x;
mat[j].push_back(last);
mat[last].push_back(j);
cap[j][last] = y;
}
// adaugam muchii intre orase cu restricitiile:
// 1. nu putem merge din oras in el insusi
// 2. nu putem avea muchia i-j daca avem deja muchia j-i
for (int i = 1; i <= n; i++) {
for (int j = n + 1; j <= n + n; j++) {
if ((i % n) != (j % n)) {
mat[i].push_back(j);
mat[j].push_back(i);
cap[i][j] = 1;
}
}
}
// afisam fluxul maxim
fout << edmonds_karp(start, last) << endl;
// afisam drumurile
for (int i = 1; i <= n; i++) {
for (int j = n + 1; j <= n + n; j++) {
if (flux[i][j] == 1)
fout << i << ' ' << j - n << endl;
}
}
fin.close();
fout.close();
return 0;
}