Pagini recente » Cod sursa (job #1768060) | Cod sursa (job #484467) | Cod sursa (job #1290160) | Cod sursa (job #2442271) | Cod sursa (job #1513238)
#include<fstream>
#include<vector>
#include<bitset>
using namespace std;
int n, i, x, y, vecin, d, minim, p, nr, j;
int c[205][205], f[205][205], s[205], t[205];
vector<int> v[205];
bitset<205> viz;
ifstream fin("harta.in");
ofstream fout("harta.out");
int bfs(){
int p, u, nod, vecin, i;
int ok = 0;
viz.reset();
p = u = 1;
t[0] = -1;
s[1] = 0;
viz[0] = 1;
while(p <= u){
nod = s[p];
for(i = 0; i < v[nod].size(); i++){
vecin = v[nod][i];
if(viz[vecin] == 0 && f[nod][vecin] < c[nod][vecin]){
viz[vecin] = 1;
u++;
s[u] = vecin;
t[vecin] = nod;
if(vecin == d){
ok = 1;
}
}
}
p++;
}
return ok;
}
int main(){
fin>> n;
d = 2 * n + 1;
for(i = 1; i <= n; i++){
fin>> x >> y;
v[0].push_back(i);
v[i].push_back(0);
c[0][i] = x;
v[n + i].push_back(d);
v[d].push_back(n + i);
c[n + i][d] = y;
}
for(i = 1; i <= n; i++){
for(j = n + 1; j <= 2 * n; j++){
if(j != n + i){
v[i].push_back(j);
v[j].push_back(i);
c[i][j] = 1;
}
}
}
while( bfs() ){
for(i = 0; i < v[d].size(); i++){
vecin = v[d][i];
if(viz[vecin] == 1 && f[vecin][d] < c[vecin][d]){
minim = c[vecin][d] - f[vecin][d];
p = vecin;
while(t[p] >= 0){
minim = min(minim, c[ t[p] ][p] - f[ t[p] ][p]);
p = t[p];
}
f[vecin][d] += minim;
f[d][vecin] -= minim;
p = vecin;
while(t[p] >= 0){
f[ t[p] ][p] += minim;
f[ p][ t[p] ] -= minim;
p = t[p];
}
}
}
}
for(i = 1; i <= n; i++){
for(j = n + 1; j <= 2 * n; j++){
if(f[i][j] == 1){
nr++;
}
}
}
fout<< nr <<"\n";
for(i = 1; i <= n; i++){
for(j = n + 1; j <= 2 * n; j++){
if(f[i][j] == 1){
fout<< i <<" "<< j - n <<"\n";
}
}
}
return 0;
}