Pagini recente » Cod sursa (job #149620) | Cod sursa (job #1224549) | Cod sursa (job #387825) | Cod sursa (job #1085257) | Cod sursa (job #2422443)
#include <iostream>
#include <fstream>
#include <queue>
#define MAXN 201
#define INF 1<<30
#define DEST 2*N + 1
#define START 0
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector<int> G[MAXN];
int C[MAXN][MAXN], F[MAXN][MAXN];
int N, M, father[MAXN];
bool bfs() {
int node, next;
bool viz[MAXN] = {false};
queue<int> Q;
Q.push(START);
viz[START] = true;
while (!Q.empty()) {
node = Q.front();
Q.pop();
for (int i = 0; i < G[node].size(); ++i) {
next = G[node][i];
if (viz[next] == false && C[node][next] != F[node][next]) {
viz[next] = true;
Q.push(next);
father[next] = node;
if (next == DEST) {
return true;
}
}
}
}
return false;
}
int main()
{
int x, y, capacity, flux_min;
int inter, exter;
f >> N;
for (int i = 1; i <= N; ++i) {
f >> exter >> inter;
C[START][i] = exter;
C[N + i][DEST] = inter;
G[START].push_back(i);
G[i].push_back(START);
G[DEST].push_back(N + i);
G[N + i].push_back(DEST);
}
for (int i = 1; i <= N; ++i) {
for (int j = N + 1; j <= 2 * N; ++j) {
if (j != N + i) {
C[i][j] = 1;
G[i].push_back(j);
G[j].push_back(i);
}
}
}
int flux = 0;
while (bfs() == true) {
flux_min = INF;
int node = DEST;
while (node != START) {
flux_min = min(flux_min, C[father[node]][node] - F[father[node]][node]);
node = father[node];
}
node = DEST;
while (node != START) {
F[father[node]][node] += flux_min;
F[node][father[node]] -= flux_min;
node = father[node];
}
flux += flux_min;
}
g << flux << '\n';
for (int i = 1; i <= N; ++i) {
for (int j = N + 1; j <= 2 * N; ++j) {
if (F[i][j] != 0) {
g << i << ' ' << j - N << '\n';
}
}
}
return 0;
}