Cod sursa(job #607324)

Utilizator SpiderManSimoiu Robert SpiderMan Data 11 august 2011 17:42:28
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
# 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);
}