Cod sursa(job #641082)

Utilizator andrei.finaruFinaru Andrei Emanuel andrei.finaru Data 27 noiembrie 2011 11:15:15
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;

int i,j,n,m,c[205][205],flux[205][205],x,y,tata[205],minim,flux_maxim,sink;
vector<int> lista[205];
queue<int> coada;
int viz[205];

ifstream f("harta.in");
ofstream g("harta.out");


int bf()
{
   memset(viz,0,sizeof(viz));
   memset(tata,0,sizeof(tata));

	int x,i,nr_vecini,vecin;
	coada.push(0);
	while(!coada.empty())
	{
		x=coada.front(); coada.pop();
		nr_vecini=lista[x].size();
		for(i=0;i<nr_vecini;i++)
		{
		    vecin=lista[x][i];
			if(!viz[vecin]&&flux[x][vecin]<c[x][vecin])
			{
				viz[vecin]=1;
				tata[vecin]=x;
				coada.push(vecin);
			}
		}
	}
    return viz[n];
}


int main()
{
	f>>n;
	sink=2*n+1;
	for(i=1;i<=n;i++)
	{
		f>>x>>y;
		lista[0].push_back(i);
		lista[i].push_back(0);
		lista[i+n].push_back(sink);
		lista[sink].push_back(i+n);
		c[0][i]=x;
		c[i+n][sink]=y;
	}
	for(i=1;i<=n;++i)
        for(j=n+1;j<sink;++j)
        if(j-i!=n)
        {
            lista[i].push_back(j);
            c[i][j]=1;
            lista[j].push_back(i);
            c[j][i]=0;
        }

	while(bf())
	{
		for(i=0;i<sink;i++)
			if(tata[i] && flux[i][sink]<c[i][sink])
			{
				minim=c[i][sink]-flux[i][sink];
				for(j=i;j!=0;j=tata[j])
					if(c[tata[j]][j]-flux[tata[j]][j]<minim)
						minim=c[tata[j]][j]-flux[tata[j]][j];

                if(minim)
					{
						flux[i][sink]=flux[i][sink]+ minim;
						flux[sink][i]=flux[sink][i]- minim;

						for(j=i;j!=0;j=tata[j])
						{
							flux[tata[j]][j]=flux[tata[j]][j]+ minim;
							flux[j][tata[j]]=flux[j][tata[j]]-minim;
						}
						flux_maxim=flux_maxim+minim;
					}
			}
	}
	g<<flux_maxim<<'\n';
	for(i=1;i<=n;++i)
        for(j=n+1;j<sink;++j)
            if(flux[i][j]) g<<i<<' '<<j-n<<'\n';

	f.close();g.close();
	return 0;
}