Cod sursa(job #578831)

Utilizator pykhNeagoe Alexandru pykh Data 11 aprilie 2011 17:28:37
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include<cstring>
#include<vector>
#include<bitset>
#include<queue>
using namespace std;

#define pb push_back

const char in[]="harta.in";
const char out[]="harta.out";

const int Max_N = 210;

vector<int>G[Max_N];
bitset<Max_N>in_Q;
queue<int>Q;

int C[Max_N][Max_N], F[Max_N][Max_N], T[Max_N], S, D, N, x, y, min_f, flow;

inline int min(int a, int b){return ( a > b ) ? b : a;}

bool BFS()
	{
		in_Q.reset();
		while(Q.size())Q.pop();
		Q.push(S);
		in_Q[S] = true;
		memset(T, 0, sizeof(T));
		
		while(Q.size())
		{
			x = Q.front();
			Q.pop();
			if(x == D)return true;
			for(unsigned i = 0 ; i < G[x].size() ; ++i)
			{
				if(C[x][G[x][i]] == F[x][G[x][i]] || in_Q[G[x][i]])continue;
				T[G[x][i]] = x;
				Q.push(G[x][i]);
				in_Q[G[x][i]] = true;
				if(G[x][i] == D) return true;
			}
		}
		return false;
}
		
		


int main()
	{
		freopen(in,"r",stdin);
		freopen(out,"w",stdout);
		scanf("%d", &N);
		
		S = 0, D = N * 2 + 1;
		
		for(int i = 1 ; i <= N ; ++i)
		{
		scanf("%d %d", &x, &y);
		G[S].pb(i);
		G[i + N].pb(D);
		G[D].pb(i + N); 
		C[S][i] = C[i][S] = x;
		C[i + N][D] = C[D][i + N] = y;
		}
		
		for(int i = 1 ; i <= N ; ++i)
			for(int j = N + 1; j < D ; ++j)
				if(i != j - N)
			{
				G[i].pb(j);
				C[i][j] = 1;
				G[j].pb(i);
			}
			
		while(BFS())
		{	
			for(unsigned i = 0 ; i < G[D].size() ; ++i){
				x = G[D][i];
				if(F[x][D] == C[x][D] || !in_Q[x])continue;
				T[D] = x;
			min_f = 0x3f3f3f3f;
			for(int i = D ; i != S ; i = T[i])
				min_f = min(min_f, C[T[i]][i] - F[T[i]][i]);
			if(!min_f)continue;
			for(int i = D ; i != S ; i = T[i])
			{
				F[T[i]][i] += min_f;
				F[i][T[i]] -= min_f;
			}
			flow += min_f;
		}
		}
		printf("%d\n", flow);
		for(int i = 1 ; i <= N ; ++i)
			for(int j = N ; j <= D ; ++j)
				if(i != j - N && F[i][j] == 1)
					printf("%d %d\n", i, j - N);
				
		return 0;
}