Cod sursa(job #319713)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 1 iunie 2009 21:32:38
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.53 kb
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#define N 	120
#define oo 	19383934
#define pb	push_back

using namespace std;

vector<int> in, out;
int c[2*N][2*N], flux[2*N][2*N];
vector<int> t, G[N * 2];
int n;

bool bf() {
        int i, j;

        queue<int> Q;//fprintf(stderr,"\n");
        Q.push(0);//printf("%s ","am intrat in bf");
        //t.resize((n<<1)+2,-1);
        //print();
        for (i = 0;i <= (n << 1) + 1;++i)
                t[i] = -1;
                
        //for (i=0;i<=(n<<1)+1;++i)
        //printf("%d ",t[i]);
        while (!Q.empty()) {
                //fprintf(stderr,"%d\n",Q.front());
                for (j = 0; j < (int) G[Q.front ()].size (); ++ j) {
                        i = G[Q.front ()][j];
                        if (flux[Q.front()][i] < c[Q.front()][i] && t[i] == -1) {
                                Q.push(i);
                                t[i] = Q.front();
                                if (i == (n << 1) + 1)
                                        return true;
                        }
                }
                Q.pop();
        }

        return false;
}

int minim() {
        int i = n << 1 + 1, m = oo;
        //printf("\n***\n");
        while (i) {
                //printf("j=%d ",i);
                if (c[t[i]][i] - flux[t[i]][i] < m)
                        m = c[t[i]][i] - flux[t[i]][i];
                //printf("(%d,%d) ",t[i],i);
                i = t[i];
        }

        return m;
}

void update(int dif) {
        int i = (n << 1) + 1;

        while (i) {
                flux[t[i]][i] += dif;
                flux[i][t[i]] -= dif;
                i = t[i];
                //printf("i=%d ",i);
        }
}

void fluxx() {
        int i, j, minx = oo;

        while (bf()) {
                //minx=minim();
                update(1);
        }
}
vector< pair<int, int> > sol;

main() {
        int i, j;
        freopen("harta.in", "r", stdin);
        freopen("harta.out", "w", stdout);

        scanf("%d", &n);
        in.resize(n + 1);
        out.resize(n + 1);
        t.resize((n << 1) + 3, - 1);

        for (i = 1; i <= n; ++ i)
                scanf("%d%d", &out[i], &in[i]);

        for (i = 1; i <= n; ++ i)
                for (j = n + 1;j <= (n << 1); ++ j)
                        if (j != i + n) {
                                c[i][j] = 1;
                                G[i].pb (j);
                                G[j].pb (i);
                        }
                        
        for (i = 1; i <= n; ++ i) {
                c[0][i] = out[i];
                if (out[i]) {
                        G[0].pb (i);
                        G[i].pb (0);
                }
        }

        for (i = n + 1; i <= (n << 1); ++ i) {
                c[i][(n<<1)+1] = in[i - n];
                if (in[i - n]) {
                        G[i].pb (2 * n + 1);
                        G[2 * n + 1].pb (i);
                }
        }

	/*for (i = 0; i <= 2 * n + 1; ++ i) {
		printf("NODE : %d = ", i);
		for (j = 0; j < (int) G[i].size (); ++ j)
			printf("%d ", G[i][j]);
		puts ("");
	}*/
        fluxx();

	/*for (i = 0; i <= 2 * n + 1; ++ i) {
		for (j = 0; j <= 2 * n + 1; ++ j)
			printf("%d ", flux[i][j]);
		puts ("");
	}
		*/
        for (i = 1; i <= n; ++ i)
                for (j = n + 1; j <= (n << 1); ++ j)
                        if (flux[i][j] == 1)
                                sol.push_back(make_pair(i, j - n));

        printf("%d\n", sol.size());

        for (i = 0; i < sol.size(); ++ i)
                printf("%d %d\n", sol[i].first, sol[i].second);
}