Pagini recente » Istoria paginii runda/zz | Istoria paginii utilizator/castiel15 | Cod sursa (job #1990506) | Cod sursa (job #1382842) | Cod sursa (job #607324)
Cod sursa(job #607324)
# include <cstdio>
# include <cstring>
# include <queue>
# include <vector>
using namespace std;
const char *FIN = "harta.in", *FOU = "harta.out";
const int MAX = 210;
vector <int> G[MAX];
vector < pair <int, int> > vec;
int N, S, D, C[MAX][MAX], F[MAX][MAX], T[MAX];
inline void getmin (int &a, int b) {
a = a < b ? a : b;
}
inline int bfs (void) {
memset (T, -1, sizeof (T)), T[S] = 0;
queue <int> Q;
for (Q.push (S); ! Q.empty (); Q.pop ()) {
int X = Q.front ();
for (vector <int> :: iterator i = G[X].begin (); i != G[X].end (); ++i)
if (T[*i] == -1 && F[X][*i] < C[X][*i])
Q.push (*i), T[*i] = X;
}
return T[D] != -1;
}
int main (void) {
freopen (FIN, "r", stdin);
freopen (FOU, "w", stdout);
scanf ("%d", &N), D = 2 * N + 2;
for (int i = 1, x, y; i <= N; ++i) {
scanf ("%d %d", &x, &y);
G[S].push_back (i), C[S][i] = C[i][S] = x;
G[i + N].push_back (D), G[D].push_back (i + N);
C[i + N][D] = C[D][i + N] = y;
}
for (int i = 1; i <= N; ++i)
for (int j = N + 1; j <= 2 * N + 1; ++j)
if (i != j - N) {
G[i].push_back (j);
G[j].push_back (i);
C[i][j] = 1;
}
for (; bfs (); ) {
for (vector <int> :: iterator i = G[D].begin (); i != G[D].end (); ++i)
if (F[*i][D] < C[*i][D]) {
int fmin = C[*i][D] - F[*i][D];
for (int j = *i; j != S; j = T[j])
getmin (fmin, C[T[j]][j] - F[T[j]][j]);
F[*i][D] += fmin, F[D][*i] -= fmin;
for (int j = *i; j != S; j = T[j])
F[T[j]][j] += fmin, F[j][T[j]] -= fmin;
}
}
for (int i = 1; i <= N; ++i)
for (int j = N + 1; j <= 2 * N + 1; ++j)
if (i != j - N && F[i][j] == 1)
vec.push_back (make_pair (i, j - N));
printf ("%d\n", vec.size ());
for (size_t i = 0; i < vec.size (); ++i)
printf ("%d %d\n", vec[i].first, vec[i].second);
}