Pagini recente » Cod sursa (job #872646) | Cod sursa (job #1921909) | Cod sursa (job #1263115) | Cod sursa (job #73496) | Cod sursa (job #1545771)
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
using namespace std;
const int SRC = 0;
const int NMAX = 202;
int DST;
vector<int> A[NMAX];
int F[NMAX][NMAX];
int C[NMAX][NMAX];
int T[NMAX];
int U[NMAX];
int In[NMAX];
int Out[NMAX];
int N;
bool drum() {
queue<int> Q;
memset(U, 0, sizeof(U));
memset(T, 0, sizeof(T));
Q.push(SRC);
T[DST] = -1;
U[SRC] = 1;
while (!Q.empty()) {
int x = Q.front();
Q.pop();
if (x == DST)
continue;
for (auto &y : A[x]) {
if (F[x][y] < C[x][y] && !U[y]) {
T[y] = x;
U[y] = 1;
Q.push(y);
}
}
}
if (T[DST] == -1)
return false;
for (auto &i : A[DST]) {
if (!U[i])
continue;
if (F[i][DST] == C[i][DST])
continue;
int fm = 0x3f3f3f3f;
T[DST] = i;
int tmp = DST;
while (tmp != SRC) {
fm = min(fm, C[T[tmp]][tmp] - F[T[tmp]][tmp]);
tmp = T[tmp];
}
tmp = DST;
while (tmp != SRC) {
F[T[tmp]][tmp] += fm;
F[tmp][T[tmp]] -= fm;
tmp = T[tmp];
}
}
return true;
}
void flux() {
while (drum());
}
int main() {
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%d %d", &Out[i], &In[i]);
}
DST = 2 * N + 1;
for (int i = 1; i <= N; i++) {
A[SRC].push_back(i);
A[i].push_back(SRC);
C[SRC][i] = Out[i];
A[DST].push_back(i+N);
A[i+N].push_back(DST);
C[i+N][DST] = In[i];
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == j)
continue;
A[i].push_back(j+N);
A[j+N].push_back(i);
C[i][j+N] = 1;
}
}
flux();
vector<pair<int, int> > Sol;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (F[i][j+N])
Sol.push_back(make_pair(i, j));
}
}
printf("%d\n", Sol.size());
for (int i = 0; i < Sol.size(); i++) {
printf("%d %d\n", Sol[i].first, Sol[i].second);
}
return 0;
}