Pagini recente » Cod sursa (job #1638849) | Cod sursa (job #1035520) | Cod sursa (job #606798) | Cod sursa (job #2733095) | Cod sursa (job #319713)
Cod sursa(job #319713)
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#define N 120
#define oo 19383934
#define pb push_back
using namespace std;
vector<int> in, out;
int c[2*N][2*N], flux[2*N][2*N];
vector<int> t, G[N * 2];
int n;
bool bf() {
int i, j;
queue<int> Q;//fprintf(stderr,"\n");
Q.push(0);//printf("%s ","am intrat in bf");
//t.resize((n<<1)+2,-1);
//print();
for (i = 0;i <= (n << 1) + 1;++i)
t[i] = -1;
//for (i=0;i<=(n<<1)+1;++i)
//printf("%d ",t[i]);
while (!Q.empty()) {
//fprintf(stderr,"%d\n",Q.front());
for (j = 0; j < (int) G[Q.front ()].size (); ++ j) {
i = G[Q.front ()][j];
if (flux[Q.front()][i] < c[Q.front()][i] && t[i] == -1) {
Q.push(i);
t[i] = Q.front();
if (i == (n << 1) + 1)
return true;
}
}
Q.pop();
}
return false;
}
int minim() {
int i = n << 1 + 1, m = oo;
//printf("\n***\n");
while (i) {
//printf("j=%d ",i);
if (c[t[i]][i] - flux[t[i]][i] < m)
m = c[t[i]][i] - flux[t[i]][i];
//printf("(%d,%d) ",t[i],i);
i = t[i];
}
return m;
}
void update(int dif) {
int i = (n << 1) + 1;
while (i) {
flux[t[i]][i] += dif;
flux[i][t[i]] -= dif;
i = t[i];
//printf("i=%d ",i);
}
}
void fluxx() {
int i, j, minx = oo;
while (bf()) {
//minx=minim();
update(1);
}
}
vector< pair<int, int> > sol;
main() {
int i, j;
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d", &n);
in.resize(n + 1);
out.resize(n + 1);
t.resize((n << 1) + 3, - 1);
for (i = 1; i <= n; ++ i)
scanf("%d%d", &out[i], &in[i]);
for (i = 1; i <= n; ++ i)
for (j = n + 1;j <= (n << 1); ++ j)
if (j != i + n) {
c[i][j] = 1;
G[i].pb (j);
G[j].pb (i);
}
for (i = 1; i <= n; ++ i) {
c[0][i] = out[i];
if (out[i]) {
G[0].pb (i);
G[i].pb (0);
}
}
for (i = n + 1; i <= (n << 1); ++ i) {
c[i][(n<<1)+1] = in[i - n];
if (in[i - n]) {
G[i].pb (2 * n + 1);
G[2 * n + 1].pb (i);
}
}
/*for (i = 0; i <= 2 * n + 1; ++ i) {
printf("NODE : %d = ", i);
for (j = 0; j < (int) G[i].size (); ++ j)
printf("%d ", G[i][j]);
puts ("");
}*/
fluxx();
/*for (i = 0; i <= 2 * n + 1; ++ i) {
for (j = 0; j <= 2 * n + 1; ++ j)
printf("%d ", flux[i][j]);
puts ("");
}
*/
for (i = 1; i <= n; ++ i)
for (j = n + 1; j <= (n << 1); ++ j)
if (flux[i][j] == 1)
sol.push_back(make_pair(i, j - n));
printf("%d\n", sol.size());
for (i = 0; i < sol.size(); ++ i)
printf("%d %d\n", sol[i].first, sol[i].second);
}