Pagini recente » Cod sursa (job #62346) | Cod sursa (job #2457633) | Cod sursa (job #837157) | Cod sursa (job #1020229) | Cod sursa (job #2589826)
#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 997
using namespace std;
const int NMAX = 105;
int N;
int father[NMAX];
int capacity[2 * NMAX][2 * NMAX];
int flow[2 * NMAX];
bool seen[2 * NMAX];
vector <int> edges[2 * NMAX];
queue <int> Q;
void read(){
scanf("%d", &N);
int a, b;
for(int i = 1; i <= N; i++){
scanf("%d%d", &a, &b);
ans += a;
capacity[0][i] = a;
edges[0].push_back(i);
edges[i].push_back(0);
capacity[N + i][2 * N + 1] = b;
edges[N + i].push_back(2 * N + 1);
edges[2 * N + 1].push_back(N + i);
for(int j = N + 1; j <= 2 * N; j++){
if(j == N + i) continue;
capacity[i][j] = 1;
edges[i].push_back(j);
edges[j].push_back(i);
}
}
}
bool bellman_ford(){
Q.push(0);
flow[0] = 2e9;
while(!Q.empty()){
int node = Q.front();
Q.pop();
for(int i = 0; i < edges[node].size(); i++){
int x = edges[node][i];
if(!capacity[node][x]) continue;
if(flow[x] < min(flow[node], capacity[node][x])){
Q.push(x);
flow[x] = min(flow[node], capacity[node][x]);
father[x] = node;
}
}
}
if(!father[2 * N + 1])
return false;
int node = 2 * N + 1;
int x = flow[2 * N + 1];
ans += x;
while(node != 0){
capacity[father[node]][node] -= x;
capacity[node][father[node]] += x;
node = father[node];
}
return true;
}
int main(){
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
read();
bool retry = true;
while(retry){
retry = false;
for(int i = 0; i <= 2 * N + 1; i++){
flow[i] = 0;
father[i] = 0;
}
retry = bellman_ford();
}
printf("%d\n", ans);
for(int i = N + 1; i <= 2 * N; i++){
for(int j = 1; j <= N; j++)
if(capacity[i][j])
printf("%d %d\n", j, i - N);
}
return 0;
}