Pagini recente » Cod sursa (job #436493) | Cod sursa (job #1020012) | Cod sursa (job #68987) | Cod sursa (job #1084517) | Cod sursa (job #2955370)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int NMAX = 100;
int N, inDeg[NMAX + 2], outDeg[NMAX + 2];
int S, D;
vector<int> g[2 * NMAX + 5];
int capacity[2 * NMAX + 5][2 * NMAX + 5], flow[2 * NMAX + 5][2 * NMAX + 5];
int bef[2 * NMAX + 5];
queue<int> Q;
bool seen[2 * NMAX + 5];
bool bfs() {
for (int i = S; i <= D; i++) { seen[i] = false; }
Q.push(S);
seen[S] = true;
while (!Q.empty()) {
int node = Q.front();
Q.pop();
for (auto it: g[node]) {
if (!seen[it] && capacity[node][it] > flow[node][it]) {
seen[it] = true;
bef[it] = node;
Q.push(it);
}
}
}
return seen[D];
}
int main() {
fin >> N;
int roads = 0;
for (int i = 1; i <= N; i++) {
fin >> outDeg[i] >> inDeg[i];
roads += outDeg[i];
}
fout << roads << '\n';
S = 0, D = 2 * N + 1;
for (int i = 1; i <= N; i++) {
g[S].push_back(i);
g[i].push_back(S);
capacity[S][i] = outDeg[i];
g[i + N].push_back(D);
g[D].push_back(i + N);
capacity[i + N][D] = inDeg[i];
for (int j = 1; j <= N; j++) {
if (i != j) {
g[i].push_back(j + N);
g[j + N].push_back(i);
capacity[i][j + N] = 1;
}
}
}
while (bfs()) {
for (auto it: g[D]) {
int pumpFlow = capacity[it][D] - flow[it][D];
for (int node = it; node != S; node = bef[node]) {
pumpFlow = min(pumpFlow, capacity[bef[node]][node] - flow[bef[node]][node]);
}
flow[it][D] += pumpFlow;
flow[D][it] -= pumpFlow;
for (int node = it; node != S; node = bef[node]) {
flow[bef[node]][node] += pumpFlow;
flow[node][bef[node]] -= pumpFlow;
}
}
}
for (int i = 1; i <= N; i++) {
for (auto it: g[i]) {
if (flow[i][it] == 1) {
fout << i << ' ' << it - N << '\n';
}
}
}
return 0;
}