Pagini recente » Cod sursa (job #1633380) | Cod sursa (job #2907067) | Cod sursa (job #2562115) | Cod sursa (job #728919) | Cod sursa (job #1442297)
#include <iostream>
#include <queue>
#include <bitset>
using namespace std;
const int INF = 1<<30;
const int NMAX = 2 * 100 + 2; // 2 noduri pt fiecare oras + super source, super sink
vector<int> adjacent[NMAX];
int capacity[NMAX][NMAX]; // speram ca se initializeaza cu zero ^^
int findPath(const int source, const int sink) {
queue<int> Q;
bitset<NMAX> visited;
Q.push(source);
visited[source] = true;
vector<int> from(NMAX, -1);
int where;
while (!Q.empty()) {
where = Q.front(); Q.pop();
for (int next: adjacent[where]) {
if (!visited[next] && capacity[where][next] > 0) {
Q.push(next);
visited[next] = 1;
from[next] = where;
if (next == sink) {
break;
}
}
}
}
// we compute the path capacity
int pathCap = INF;
where = sink;
while (from[where] != -1) {
int prev = from[where]; // the prev vertex
pathCap = min(pathCap, capacity[prev][where]);
where = prev;
}
// we update the residual network; if no path is found the while
// loop will not be entered
where = sink;
while (from[where] > -1) {
int prev = from[where];
capacity[prev][where] -= pathCap;
capacity[where][prev] += pathCap;
where = prev;
}
// if no path is found, path_cap is infinity
if (pathCap == INF) {
return 0;
} else {
return pathCap;
}
}
int maxFlow(const int source, const int sink) {
int result = 0, pathCap;
do {
pathCap = findPath(source, sink);
if (pathCap != 0) {
result += pathCap;
}
} while (pathCap != 0);
return result;
}
int main() {
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
int N; scanf("%d", &N);
int SSOURCE = 0;
int SSINK = 2 * N + 1;
for (int v = 1; v <= N; v++) {
int degOut, degIn;
scanf("%d %d\n", °Out, °In);
adjacent[SSOURCE].push_back(v);
adjacent[v].push_back(SSOURCE);
capacity[SSOURCE][v] = degOut;
int u = v + N;
adjacent[u].push_back(SSINK);
adjacent[SSINK].push_back(u);
capacity[u][SSINK] = degIn;
// formeaza drum catre fiecare alt oras
for (int u = N + 1; u <= 2 * N; u++) {
if (u == (v + N)) continue;
adjacent[v].push_back(u);
adjacent[u].push_back(v);
capacity[v][u] = 1;
}
}
printf("%d\n", maxFlow(SSOURCE, SSINK));
for (int v = 1; v <= N; v++) {
for (int u: adjacent[v]) {
if (capacity[v][u] == 0 && capacity[u][v] == 1 && u != SSINK) {
printf("%d %d\n", v, u - N);
}
}
}
return 0;
}