Pagini recente » Cod sursa (job #149313) | Cod sursa (job #2773177) | Cod sursa (job #2645118) | Cod sursa (job #218055) | Cod sursa (job #540004)
Cod sursa(job #540004)
#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;
vector<int> a[N];
int BFS() {
int k, i, j;
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];
for(i = 0; i < a[k].size(); ++i)
if(c[k][a[k][i]] > f[k][a[k][i]] && !v[a[k][i]]) {
t[a[k][i]] = k;
v[a[k][i]] = 1;
cd[++cd[0]] = a[k][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], a[0].push_back(i), a[i].push_back(0), a[n + i].push_back(2 * n + 1), a[2 * n + 1].push_back(n + i);
t[0] = -1;
for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
if(i != j)
c[i][n + j] = 1, a[i].push_back(n + j), a[n + j].push_back(i);
S = 0;
D = 2 * n + 1;
int u;
for(;BFS();) {
// printf("\n");
for(i = n + 1; i <= 2 * n; ++i)
if(v[i]) {
k = D;
t[k] = i;
r = INF;
while(k) {
r = min(r,c[t[k]][k] - f[t[k]][k]);
// printf("%d ", k);
k = t[k];
}
// printf("%d\n", r);
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] == c[i][j + n] && f[i][j + n] > 0)
++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;
}