Cod sursa(job #791731)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 24 septembrie 2012 23:25:20
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <vector>
#include <queue>
#define NMAx 210
using namespace std;

queue <int> Q;
vector <int> G[NMAx];
int N,S,D,paint,Sum,T[NMAx];
int viz[NMAx],Flux[NMAx][NMAx];

bool BF() {
	
	int i,Nod,Vecin;
	
	Q.push(S);
	++paint;
	viz[S]=paint;
	
	while(!Q.empty()) {
		
		Nod=Q.front();
		Q.pop();
		
		for(i=0;i<G[Nod].size();i++) {
			
			Vecin=G[Nod][i];
			if(Flux[Nod][Vecin]&&viz[Vecin]!=paint) {
				T[Vecin]=Nod;
				Q.push(Vecin);
				viz[Vecin]=paint;
				}
			}
		}
	
	return (viz[D]==paint);
	
}
void BuildGraph() {
	
	int i,j;
	
	for(i=1;i<=N;i++)
		for(j=N+1;j<D;j++)
			if(i!=(j-N)) {
				Flux[i][j]=1;
				G[i].push_back(j);
				G[j].push_back(i);
				}
	
}
void Solve() {
	
	int i;
	BuildGraph();
	
	while(BF()) {
		
		for(i=D;i;i=T[i]) {
			Flux[T[i]][i]--;
			Flux[i][T[i]]++;
			}
		
		}
	
}
void Citire() {
	
	ifstream in("harta.in");
	in>>N;
	
	S=0;
	D=2*N+1;
	
	for(int i=1;i<=N;i++) {
		in>>Flux[S][i]>>Flux[i+N][D];
		Sum+=Flux[S][i]+Flux[i+N][D];
		G[S].push_back(i);
		G[i+N].push_back(D);
		}
	
	in.close();
	
}
void Afis() {
	
	int i,j;
	ofstream out("harta.out");
	out<<(Sum/2)<<'\n';
	
	for(i=1;i<=N;i++)
		for(j=0;j<G[i].size();j++)
			if(!Flux[i][G[i][j]])
				out<<i<<' '<<(G[i][j]-N)<<'\n';
				
	out.close();
	
}
int main() {
	
	Citire();
	Solve();
	Afis();
	
	return 0;
	
}