Cod sursa(job #790866)

Utilizator S7012MYPetru Trimbitas S7012MY Data 22 septembrie 2012 15:40:59
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define DN 305
using namespace std;

typedef vector<int>::iterator it;
int n,cap[DN][DN],fl[DN][DN],pre[DN],s,d;
vector<int> gr[DN];

bool bfs() {
	memset(pre,-1,sizeof(pre));
	pre[s]=-2;
	queue<int> c;
	for(c.push(s); c.size(); c.pop()) {
		int fr=c.front();
		for(int i=s; i<=d; ++i) if(-1==pre[i] && cap[fr][i]>fl[fr][i]) {
			c.push(i);
			pre[i]=fr;
		}
	}
	return pre[d]!=-1;
}


int main()
{
    ifstream f("harta.in");
	ofstream g("harta.out");
	f>>n;
	d=2*n+2;
	for(int i=1; i<=n; ++i) {
	    int a,b;
	    f>>a>>b;
	    cap[s][i]=a;
	    cap[i+n][d]=b;
	    for(int j=1; j<=n; ++j) if(j!=i) ++cap[i][j+n];
	}

	int r=0,c;
	for(;bfs();) {
		for(int i=1; i<=d; ++i) if(fl[i][d]<cap[i][d]) {
			c=cap[i][d]-fl[i][d];
			for(int y=i;pre[y]!=-2;y=pre[y]) c=min(c,cap[pre[y]][y]-fl[pre[y]][y]);
			r+=c;
			fl[i][d]+=c;
			fl[d][i]-=c;
			for(int y=i;pre[y]!=-2;y=pre[y]) {
				fl[pre[y]][y]+=c;
				fl[y][pre[y]]-=c;
			}
		}
	}
	g<<r<<'\n';
	for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) if(fl[i][j+n]) {
	    g<<i<<' '<<j<<'\n';
	}
    return 0;
}