Cod sursa(job #1741168)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 13 august 2016 03:26:24
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 1.36 kb
#include <fstream>
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string>
#define pb push_back
#define NMAX 205

using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

int in[NMAX],out[NMAX],C[NMAX][NMAX],F[NMAX][NMAX],viz[NMAX],Prev[NMAX],sink;
vector<int> v[NMAX];

int BFS() {
	int i,x,y;

	queue<int> Q;
	memset(viz,0,sizeof(viz));
	viz[0]=1;
	Q.push(0);
	while(!Q.empty()) {
		x=Q.front();
		Q.pop();

		//if(x==sink) return 1;

		for(i=0;i<v[x].size();++i) {
			y=v[x][i];

			if(!viz[y] && C[x][y] > F[x][y]) {
				Prev[y]=x;
				viz[y]=1;
				Q.push(y);
			}
		}
	}

	return viz[sink];
}

int main() {
	int n,i,j,x,y,q,m=0,fmin,p;

	fin>>n;
	sink=2*n+1;
	for(i=1;i<=n;++i) {
		fin>>out[i]>>in[i];
		m+=out[i];

		v[0].pb(i);
		v[i+n].pb(sink);
		C[0][i]=in[i];
		C[i+n][sink]=out[i];
	}

	for(i=1;i<=n;++i) {
		for(j=n+1;j<sink;++j) {
			if(i==j-n) continue;

			C[i][j]=1;
			v[j].pb(i);
			v[i].pb(j);
		}
	}

	while(BFS()) {
		p=sink;

		while(p!=0) {
			++F[Prev[p]][p];
			--F[p][Prev[p]];
			p=Prev[p];
		}
	}

	fout<<m<<'\n';
	for(i=1;i<=n;++i)
        for(j=n+1;j<sink;++j)
            if(F[i][j]==1)
                fout<<j-n<<' '<<i<<'\n';

	return 0;
}