Pagini recente » Cod sursa (job #1259278) | Cod sursa (job #2071075) | Cod sursa (job #1860141) | Borderou de evaluare (job #1553669) | Cod sursa (job #2071015)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int inf = 2000000000;
int n, src, dr;
int cap[204][204], drum[204][204], flow[204][204];
queue <int> q;
int dist[204];
int bfs() {
memset(dist, 0, sizeof(dist));
q.push(src);
dist[src] = 2;
while(!q.empty()) {
int from = q.front();
for(int k = 0; k < n; ++ k) {
if(drum[from][k] == 1) {
if(dist[k] == 0 && flow[from][k] < cap[from][k]) {
dist[k] = dist[from] + 1;
q.push(k);
}
}
}
q.pop();
}
return (dist[dr] > 0);
}
int minim(int a, int b) {
if(a > b)
return b;
return a;
}
int rem[204];
int dfs(int from, int minflow) {
if(from == dr) {
return minflow;
} else {
for(int k = rem[from]; k < n; ++ k) {
if(drum[from][k] == 1) {
if(dist[from] == dist[k] - 1) {
int deltaflow = dfs(k, minim(minflow, cap[from][k] - flow[from][k]));
if(deltaflow > 0) {
flow[from][k] += deltaflow;
flow[k][from] -= deltaflow;
rem[from] = k + 1;
return deltaflow;
}
}
}
}
return 0;
}
}
int maxflow() {
int raspuns = 0, deltaflow;
while(bfs() == 1) {
memset(rem, 0, sizeof(rem));
do {
deltaflow = dfs(src, inf);
raspuns += deltaflow;
}while(deltaflow > 0);
}
return raspuns;
}
int main() {
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d", &n);
n *= 2;
src = n ++;
dr = n ++;
for(int i = 0; i < n - 2; i += 2) {
int out, in;
scanf("%d%d", &out, &in);
drum[i][dr] = 1;
drum[dr][i] = 1;
cap[i][dr] = in;
drum[src][i + 1] = 1;
drum[i + 1][src] = 1;
cap[src][i + 1] = out;
}
for(int i = 0; i < n - 2; i += 2) {
for(int j = 0; j < n - 2; j += 2) {
if(j != i) {
drum[i + 1][j] = 1;
drum[j][i + 1] = 1;
cap[i + 1][j] = 1;
}
}
}
printf("%d\n", maxflow());
for(int i = 1; i < n - 2; i += 2) {
for(int j = 0; j < n; ++ j) {
if(flow[i][j] > 0) {
printf("%d %d\n", i / 2 + 1, j / 2 + 1);
}
}
}
return 0;
}