Pagini recente » Cod sursa (job #746526) | Cod sursa (job #948907) | Cod sursa (job #1939921) | Cod sursa (job #1186854) | Cod sursa (job #2594699)
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int NMAX = 100;
const int INF = 1000000000;
bool uz[2 * NMAX + 5];
int n, s, t, nrm;
int from[2 * NMAX + 5];
int cf[2 * NMAX + 5][2 * NMAX + 5];
queue<int> q;
bool bfs(int start) {
for(int i = s; i <= t; i++)
uz[i] = false;
q.push(start);
uz[start] = true;
from[start] = -1;
while(!q.empty()) {
int nod = q.front();
q.pop();
if(nod == t)
continue;
for(int i = s; i <= t; i++)
if(!uz[i] && cf[nod][i] > 0) {
from[i] = nod;
q.push(i);
uz[i] = true;
}
}
return uz[t];
}
void update_flux() {
int minf = INF;
for(int i = t; from[i] != -1; i = from[i])
minf = min(minf, cf[from[i]][i]);
if(minf == 0)
return;
for(int i = t; from[i] != -1; i = from[i]) {
cf[from[i]][i] -= minf;
cf[i][from[i]] += minf;
}
}
void flux() {
while(bfs(s))
for(int i = n + 1; i <= 2 * n; i++)
if(uz[i] && cf[i][t]) {
from[t] = i;
update_flux();
}
}
int main() {
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
int x, y;
scanf("%d", &n);
s = 0;
t = 2 * n + 1;
for(int i = 1; i <= n; i++) {
scanf("%d %d", &x, &y);
nrm += x;
cf[s][i] += x;
cf[n + i][t] += y;
}
for(int i = 1; i <= n; i++)
for(int j = n + 1; j <= 2 * n; j++)
if(i != j - n)
cf[i][j] = 1;
flux();
printf("%d\n", nrm);
for(int i = 1; i <= n; i++)
for(int j = n + 1; j <= 2 * n; j++)
if(i != j - n && cf[i][j] == 0)
printf("%d %d\n", i, j - n);
return 0;
}