Cod sursa(job #792186)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 26 septembrie 2012 18:14:02
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;
const int NMAX = 202;
int capacity[NMAX][NMAX],flux[NMAX][NMAX],viz[NMAX],c[NMAX*NMAX],p[NMAX];
vector <int> v[NMAX];
vector < pair < int , int > > m;
int bfs(int n)
{
	int st,dr,nod;
	st=1;
	dr=1;
	c[st]=0;
	memset(viz,0,sizeof(viz));
	viz[0]=1;
	while(st<=dr) {
		nod=c[st];
		st++;
		for(vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++)
			if(viz[*it]==0 && capacity[nod][*it]>flux[nod][*it]) {
				viz[*it]=1;
				c[++dr]=*it;
				p[*it]=nod;
				if(*it==(2*n+1))
					return 1;
			}
	}
	return 0;
}
void scrie(int n)
{
	int i,j;
	for(i=1;i<=n;i++) {
		for(j=1;j<=n;j++)
			cout<<flux[i][j+n]<<" ";
		cout<<endl;
	}
	cout<<endl;
}
void graf(int n)
{
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++) 
			if(i!=j) {
				capacity[i][j+n]=1;
				v[i].push_back(j+n);
				v[j+n].push_back(i);
			}
	for(i=1;i<=n;i++) {
		v[0].push_back(i);
		v[i].push_back(0);
		v[i+n].push_back(2*n+1);
		v[2*n+1].push_back(i+n);
	}
}
int main ()
{
	int n,i,j,in,out,fluxcurent,nod;
	ifstream f("harta.in");
	ofstream g("harta.out");
	f>>n;
	graf(n);
	for(i=1;i<=n;i++) {
		f>>out>>in;
		capacity[0][i]=out;
		capacity[i+n][2*n+1]=in;
	}
	f.close();
	while(bfs(n)) {
		for(nod=2*n+1;nod!=0;nod=p[nod]) {
			flux[p[nod]][nod]++;
			flux[nod][p[nod]]--;
		}
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(flux[i][j+n]==1)
				m.push_back(make_pair(i,j));
	g<<m.size()<<'\n';
	for(vector < pair < int , int > > :: iterator it=m.begin();it!=m.end();it++)
		g<<it->first<<" "<<it->second<<'\n';
	g.close();
	return 0;
}