Pagini recente » Cod sursa (job #1787154) | Cod sursa (job #2563955) | Cod sursa (job #2322416) | Cod sursa (job #919768) | Cod sursa (job #1508929)
#include <fstream>
#include <vector>
#include <deque>
#define DIM 102
using namespace std;
int C[2*DIM][2*DIM], F[2*DIM][2*DIM], U[2*DIM], T[2*DIM], minim;
vector<int> L[2*DIM];
deque<int> q;
int in, out, i, j, p, u, n, nod, vecin, flux;
int bfs() {
int gasit = 0;
for (int i=0;i<=2*n+1;i++)
U[i] = 0;
U[0] = 1;
q.push_back(0);
while (!q.empty()) {
nod = q.front();
for (int i=0;i<L[nod].size();i++) {
int vecin = L[nod][i];
if (U[vecin] == 0 && C[nod][vecin] > F[nod][vecin]) {
q.push_back(vecin);
U[vecin] = 1;
T[vecin] = nod;
if (vecin == 2*n+1)
gasit = 1;
}
}
q.pop_front();
}
return gasit;
}
int main () {
ifstream fin("harta.in");
ofstream fout("harta.out");
fin>>n;
for (i=1;i<=n;i++) {
fin>>out>>in;
C[0][i] = out;
L[0].push_back(i);
L[i].push_back(0);
C[n+i][2*n+1] = in;
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) {
C[i][n+j] = 1;
L[i].push_back(n+j);
L[n+j].push_back(i);
}
while (bfs()) {
for (int i=0;i<L[2*n+1].size();i++) {
p = L[2*n+1][i];
if (C[p][2*n+1] > F[p][2*n+1] && U[p] == 1) {
minim = C[p][2*n+1] - F[p][2*n+1];
u = p;
while (u!= 0) {
if ( C[ T[u] ][u] - F[ T[u] ][u] < minim) {
minim = C[ T[u] ][u] - F[ T[u] ][u];
}
u = T[u];
}
flux += minim;
F[p][2*n+1] += minim;
F[2*n+1][p] -= minim;
u = p;
while (u != 0) {
F[ T[u] ][u] += minim;
F[ u ][ T[u] ] -= minim;
u = T[u];
}
}
}
}
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;
}