Pagini recente » Cod sursa (job #2854267) | Cod sursa (job #2601424) | Cod sursa (job #2765006) | Cod sursa (job #2297695) | Cod sursa (job #2956156)
#include <fstream>
#include <queue>
using namespace std;
const int maxN = 256;
const int infi = 1 << 30;
struct Muchie {
int src, dest;
int flx, cap;
Muchie (int _src = 0, int _dest = 0, int _flx = 0, int _cap = 0):
src(_src), dest(_dest), flx(_flx), cap(_cap) { }
} father[maxN];
vector<Muchie> G[maxN];
int cost[maxN];
bool bfs(int N) {
for (int i = 0; i <= 2 * N + 1; i ++) {
cost[i] = infi;
father[i] = Muchie(-1);
}
queue<int> q;
cost[0] = 0; q.push(0);
while(!q.empty()) {
int top = q.front(); q.pop();
for (auto it: G[top]) {
if (cost[top] + 1 < cost[it.dest] && it.flx < it.cap) {
cost[it.dest] = cost[top] + 1;
father[it.dest] = it;
q.push(it.dest);
}
}
}
return cost[2 * N + 1] != infi;
}
int main() {
ifstream in("harta.in");
ofstream out("harta.out");
int N;
in >> N;
for (int i = 1; i <= N; i ++) {
int gr_int, gr_ext;
in >> gr_ext >> gr_int;
G[0].push_back(Muchie(0, i, 0, gr_ext));
G[i].push_back(Muchie(i, 0, 0, 0));
G[i + N].push_back(Muchie(i + N, 2 * N + 1, 0, gr_int));
G[2 * N + 1].push_back(Muchie(2 * N + 1, i + N, 0, 0));
}
for (int i = 1; i <= N; i ++) {
for (int j = N + 1; j <= 2 * N; j ++) {
if (i + N != j) {
G[i].push_back(Muchie(i, j, 0, 1));
G[j].push_back(Muchie(j, i, 0, 0));
}
}
}
vector<Muchie> drum;
while(bfs(N)) {
drum.clear();
int x = 2 * N + 1;
while(father[x].src != -1) {
drum.push_back(father[x]);
x = father[x].src;
}
int max_flow = infi;
for (auto it: drum)
max_flow = min(max_flow, it.cap - it.flx);
for (auto edge: drum) {
bool found = false;
for (int i = 0; i < G[edge.src].size() && !found; i ++) {
if (G[edge.src][i].dest == edge.dest) {
G[edge.src][i].flx += max_flow;
found = true;
}
}
found = false;
for (int i = 0; i < G[edge.dest].size() && !found; i ++) {
if (G[edge.dest][i].dest == edge.src) {
G[edge.dest][i].flx -= max_flow;
found = true;
}
}
}
}
int flux = 0;
for (auto it: G[0])
flux += it.flx;
out << flux << '\n';
for (int i = 1; i <= N; i ++) {
for (auto it: G[i]) {
if (it.flx == it.cap && it.dest > N && it.flx != 0) {
out << it.src << ' ' << it.dest - N << '\n';
}
}
}
return 0;
}