Pagini recente » Cod sursa (job #2219297) | Cod sursa (job #1015998) | Cod sursa (job #495781) | Cod sursa (job #2592309) | Cod sursa (job #2660787)
#include <fstream>
#include <bitset>
#include <vector>
#define DIM 210
#define INF 1000000000
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
int n,i,j,x,y,frunza,dif,flux;
vector <int> L[DIM];
int Q[DIM],c[DIM][DIM],f[DIM][DIM],t[DIM];
bitset <DIM> v;
int bfs() {
int p,u;
v.reset();
p = u = 1;
Q[1] = 0;
v[0] = 1;
int dest = 0;
while (p <= u){
for (int i=0;i<L[ Q[p] ].size();i++){
int vecin = L[ Q[p] ][i];
if (v[vecin] == 0 && c[ Q[p] ][vecin] > f[ Q[p] ][vecin]) {
u++;
Q[u] = vecin;
v[vecin] = 1;
t[vecin] = Q[p];
if (vecin == 2*n+1)
dest = 1;
}
}
p++;
}
return dest;
}
int main (){
fin>>n;
for (i=1;i<=n;i++){
fin>>x>>y;
L[0].push_back (i);
L[i].push_back (0);
L[n+i].push_back (2*n+1);
L[2*n+1].push_back (n+i);
c[0][i] = x;
c[n+i][2*n+1] = y;
}
/// punem muchie intre fiecare cu fiecare
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (i != j){
L[i].push_back (n+j);
L[n+j].push_back (i);
c[i][n+j] = 1;
}
while (bfs()) {
for (int i=0; i<L[2*n+1].size(); i++) {
frunza = L[2*n+1][i];
if (c[frunza][2*n+1] <= f[frunza][2*n+1])
continue;
dif = c[frunza][2*n+1] - f[frunza][2*n+1];
x = frunza;
while (x != 0){
dif = min (dif,c[t[x]][x]-f[t[x]][x]);
x = t[x];
}
flux += dif;
/// marim fluxurile
f[frunza][2*n+1] += dif;
f[2*n+1][frunza] -= dif;
x = frunza;
while (x != 0){
f[ t[x] ][x] += dif;
f[x][ t[x] ] -= dif;
x = t[x];
}
}
}
fout<<flux<<"\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;
}