Pagini recente » Cod sursa (job #193372) | Cod sursa (job #1928946) | Cod sursa (job #2105281) | Cod sursa (job #1053546) | Cod sursa (job #2084958)
#include<fstream>
#include<vector>
using namespace std;
ifstream in ("harta.in");
ofstream out ("harta.out");
const int dim = 105;
int a,s,f,b,n,sol,vecin,x,minim;
int graf[dim*2],vec[2*dim],tata[2*dim];
int cap[dim][dim*2], flux[dim][dim*2];
vector<int>v[2*dim];
bool bfs (void) {
for (int i = s; i <= f; i ++) {
graf[i] = 0;
}
bool ok = false;
vec[1] = s;
graf[s] = 1;
tata[s] = -1;
for (int st = 1, dr = 1; st <= dr; st ++) {
a = vec[st];
for (int i = 0; i < v[a].size(); i ++) {
b = v[a][i];
if (cap[a][b] > flux[a][b] && graf[b] == 0) {
if (b != f) {
vec[++dr] = b;
graf[b] = 1;
tata[b] = a;
}
else{
ok = true;
tata[b] = a;
}
}
}
}
return ok;
}
int main (void) {
in >> n;
s = 0; f = n * 2 + 1;
for (int i = 1; i <= n; i ++) {
in >> a >> b;
v[s].push_back (i);
v[i].push_back (s);
cap[s][i] = a;
v[i+n].push_back (f);
v[f].push_back (i+n);
cap[i+n][f] = b;
sol += a;
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
if (i != j) {
v[i].push_back (j+n);
v[j+n].push_back (i);
cap[i][j+n] = 1;
}
}
}
while (bfs()) {
for (int i = 0; i < v[f].size(); i ++) {
vecin = v[f][i];
if (cap[vecin][f] > flux[vecin][f]) {
minim = cap[vecin][f] - flux[vecin][f];
x = vecin;
while (tata[x] != -1) {
minim = min(minim, cap[tata[x]][x] - flux[tata[x]][x]);
x = tata[x];
}
x = vecin;
while (tata[x] != -1) {
flux[tata[x]][x] += minim;
flux[x][tata[x]] -= minim;
x = tata[x];
}
flux[vecin][f] += minim;
flux[f][vecin] -= minim;
}
}
}
out << sol <<"\n";
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
if (flux[i][j+n] == 1) {
out << i <<" "<< j<<"\n";
}
}
}
return 0;
}