Pagini recente » Cod sursa (job #2304189) | Cod sursa (job #2144153) | Cod sursa (job #660098) | Cod sursa (job #2837682) | Cod sursa (job #540008)
Cod sursa(job #540008)
#include<cstdio>
#include<vector>
using namespace std;
const int N = 205;
const int INF = 0x3f3f3f3f;
int n, dint[N], dies[N], c[N][N], f[N][N], t[N], v[N], S, D;
int BFS() {
int k, i, j, p, u;
int cd[N];
cd[0] = 1;
cd[1] = S;
for(i = 1; i <= 2 * n + 1; ++i)
v[i] = t[i] = 0;
v[S] = 1;
for(j = 1; j <= cd[0]; ++j) {
k = cd[j];
p = 1;
u = 2 * n + 1;
for(i = p; i <= u; ++i)
if(c[k][i] > f[k][i] && !v[i]) {
t[i] = k;
v[i] = 1;
if(i == 2 * n + 1)
return 1;
cd[++cd[0]] = i;
}
}
return v[D];
}
int main() {
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
int i, j, k, r;
scanf("%d", &n);
for(i = 1; i <= n; ++i)
scanf("%d %d", &dies[i], &dint[i]);
for(i = 1; i <= n; ++i)
c[0][i] = dies[i], c[n + i][2 * n + 1] = dint[i];
t[0] = -1;
for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
if(i != j)
c[i][n + j] = 1;
S = 0;
D = 2 * n + 1;
int u;
for(;BFS();) {
k = D;
r = INF;
while(k) {
r = min(r,c[t[k]][k] - f[t[k]][k]);
k = t[k];
}
k = D;
while(k) {
f[k][t[k]] -= r;
f[t[k]][k] += r;
k = t[k];
}
}
int nr = 0;
for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
if(f[i][j + n] == 1)
++nr;
printf("%d\n", nr);
for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
if(f[i][j + n] == 1)
printf("%d %d\n", i, j);
return 0;
}