Pagini recente » Cod sursa (job #3214970) | Cod sursa (job #1272077) | Cod sursa (job #1669842) | Cod sursa (job #2465556) | Cod sursa (job #2959710)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <fstream>
#include <set>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
#define N 201
int n, m, e, maxFlow;
int s, t;
vector<vector<int>> pairOfA(N);
int capacity[N][N];
vector<vector<int>> l(N, vector<int>());
vector<int> parent(N);
set<pair<int, int>> edges;
int inDegree[N], outDegree[N];
//O(N * M2)
int bfs(int s, int t) {
parent[s] = -2; // orice != -1 si [0,n+m+1]
queue<pair<int, int>> q;
q.push({ s, 1e9 });
while (!q.empty()) {
int cur = q.front().first;
int maxFlow = q.front().second;
q.pop();
for (int next : l[cur]) {
if (parent[next] == -1 && capacity[cur][next]) {
parent[next] = cur;
int bottleneck = min(maxFlow, capacity[cur][next]);
if (next == t)
return bottleneck;
q.push({ next, bottleneck });
}
}
}
return 0;
}
void read() {
fin >> n;
m = n;
for (int i = 1; i <= n; i++)
fin >> outDegree[i] >> inDegree[i];
}
int main() {
read();
s = 0; t = n + m + 1;
for (int i = 1; i <= n; i++) { // concectam sursa la nodurile din A cu valoarea gradului de iesire
l[s].push_back(i);
l[i].push_back(s);
capacity[s][i] = outDegree[i];
}
for (int i = n + 1; i <= n + m; i++) { // concectam nodurile din B la destinatie cu valoarea gradului de intrare
l[i].push_back(t);
l[t].push_back(i);
capacity[i][t] = inDegree[i - n];
}
for(int i = 1; i <= n; i++)
for (int j = n + 1; j <= n + m; j++) {
if (j - n == i) // nu vrem muchie de la un nod la el insusi
continue;
l[i].push_back(j);
l[j].push_back(i);
capacity[i][j] = 1;
}
for (int i = 0; i <= n + m + 1; i++) // resetam parintii
parent[i] = -1;
int bottleneck;
while (bottleneck = bfs(s, t)) { // cat mai sunt path uri care mai accepta flux
maxFlow += bottleneck;
int node = t;
while (node != s) { // mergem inapoi pe path ul gasit
int prev = parent[node];
capacity[prev][node] -= bottleneck; // muchia de inaintare pierde din spatiu exact bottleneck
capacity[node][prev] += bottleneck; // muchia de retur poate face undo cu exact bottleneck mai mult
if (node > s && node < t && prev > s && prev < t) {
if (prev < node) {
pairOfA[prev].push_back(node);
}
else {
for (int aux = 0; aux < pairOfA[node].size(); ++aux) // daca e muchie de intoarcere scot muchia prev->node
if (pairOfA[node][aux] == prev) {
pairOfA[node].erase(pairOfA[node].begin() + aux);
break;
}
}
}
node = prev;
}
for (int i = 0; i <= n + m + 1; i++) // resetam parintii
parent[i] = -1;
}
fout << maxFlow << "\n";
for (int i = 1; i <= n; i++)
for(auto j : pairOfA[i])
fout << i << " " << j - n << "\n";
return 0;
}