Pagini recente » Cod sursa (job #876846) | Cod sursa (job #2572440) | Cod sursa (job #1474043) | Cod sursa (job #3039751) | Cod sursa (job #2469718)
#include <bits/stdc++.h>
#define DIM 205
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
int n, i, j, x, y, nod, u, minim, fluxsol;
int t[DIM];
int capacitate[DIM][DIM], flux[DIM][DIM];
bitset <DIM> f;
vector <int> L[DIM];
deque <int> q;
int bfs (){
int nod, vecin;
f.reset();
f[0] = 1;
q.push_back(0);
while (!q.empty()){
nod = q.front();
q.pop_front();
for (int i=0; i<L[nod].size(); i++){
vecin = L[nod][i];
if (f[vecin] == 0 && capacitate[nod][vecin] > flux[nod][vecin]){
f[vecin] = 1;
q.push_back(vecin);
t[vecin] = nod;
}
}
}
return f[2*n+1];
}
int main(){
fin >> n;
for (i=1; i<=n; i++){
fin >> x >> y;
capacitate[0][i] = x;
L[0].push_back(i);
L[i].push_back(0);
capacitate[n+i][2*n+1]=y;
L[n+i].push_back(2*n+1);
L[2*n+1].push_back(n+i);
}
for (i=1; i<=n; i++){
for (j=1; j<=n; j++){
if (i != j){
capacitate[i][n+j] = 1;
L[n+j].push_back(i);
L[i].push_back(n+j);
}
}
}
while (bfs()){
for (i=0; i<L[2*n+1].size(); i++){
nod = L[2*n+1][i];
if (capacitate[nod][2*n+1] > flux[nod][2*n+1] && f[nod] == 1){
minim = capacitate[nod][2*n+1] - flux[nod][2*n+1];
u = nod;
while (u){
minim = min (minim, capacitate[t[u]][u] - flux[t[u]][u]);
u = t[u];
}
fluxsol += minim;
flux[nod][2*n+1] += minim;
flux[2*n+1][nod] -= minim;
u = nod;
while (u){
flux[t[u]][u] += minim;
flux[u][t[u]] -= minim;
u = t[u];
}
}
}
}
fout << fluxsol << "\n";
for (i=1; i<=n; i++){
for (j=n+1; j<=2*n; j++){
if (flux[i][j] == 1){
fout << i << " " << j -n << "\n";
}
}
}
return 0;
}