Pagini recente » Cod sursa (job #1281297) | Cod sursa (job #366589) | Cod sursa (job #1044894) | Cod sursa (job #2110896) | Cod sursa (job #2109670)
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
const int INF = 2e9;
const int MAXN = 1e2;
std::vector <int> g[2 * MAXN + 1];
int flow[2 * MAXN + 1][2 * MAXN + 1], cap[2 * MAXN + 1][2 * MAXN + 1],
fath[2 * MAXN + 1];
bool vis[2 * MAXN + 1];
std::queue <int> q;
static inline int min(int a, int b) {
return a > b ? b : a;
}
bool bfs(int n) {
int u;
memset(vis, 0x00, sizeof(vis));
vis[0] = 1;
q.push(0);
while (!q.empty()) {
u = q.front();
if (u != n) {
for (auto v: g[u]) {
if (!vis[v] && flow[u][v] < cap[u][v]) {
vis[v] = 1;
fath[v] = u;
q.push(v);
}
}
}
q.pop();
}
return vis[n];
}
int main() {
int n, u, v, in, out, s, d, fl, maxfl;
FILE *f = fopen("harta.in", "r");
fscanf(f, "%d", &n);
s = 0;
d = 2 * n + 1;
for (int i = 1; i <= n; ++i) {
fscanf(f, "%d%d", &in, &out);
g[s].push_back(i);
g[i].push_back(s);
cap[s][i] = in;
g[d].push_back(i + n);
g[i + n].push_back(d);
cap[i + n][d] = out;
for (int j = 1; j <= n; ++j) {
if (i ^ j) {
g[i].push_back(j + n);
g[j + n].push_back(i);
cap[i][j + n] = 1;
}
}
}
fclose(f);
maxfl = 0;
while (bfs(d)) {
for (auto u: g[d]) {
if (vis[u] && flow[u][d] < cap[u][d]) {
fath[d] = u;
fl = INF;
v = d;
while (v > 0) {
fl = min(fl, cap[fath[v]][v] - flow[fath[v]][v]);
v = fath[v];
}
v = d;
while (v > 0) {
flow[fath[v]][v] += fl;
flow[v][fath[v]] -= fl;
v = fath[v];
}
maxfl += fl;
}
}
}
f = fopen("harta.out", "w");
fprintf(f, "%d\n", maxfl);
for (int i = 1; i <= n; ++i) {
for (int j = n + 1; j <= 2 * n; ++j) {
while (flow[i][j] > 0) {
fprintf(f, "%d %d\n", i, j - n);
--flow[i][j];
}
}
}
fclose(f);
return 0;
}