Cod sursa(job #418185)

Utilizator otilia_sOtilia Stretcu otilia_s Data 15 martie 2010 16:45:48
Problema Flux maxim de cost minim Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <cstdio>
#include <vector>
using namespace std;
#define NMAX 400
#define oo 2000000000
int n,S,D;
vector <int> A[NMAX];
int nv[NMAX],Dist[NMAX], viz[NMAX],Q[NMAX];
int C[NMAX][NMAX],F[NMAX][NMAX], Cost[NMAX][NMAX];
bool inq[NMAX],Drum;

void citire()
{
	FILE *fin=fopen("fmcm.in","r");	
	int m;
	fscanf(fin,"%d%d%d%d",&n,&m,&S,&D);	
	for (int i=0;i<m;++i)
	{ int x,y,cap,z;
		fscanf(fin,"%d%d%d%d",&x,&y,&cap,&z);		
		A[x].push_back(y);
		A[y].push_back(x);
		C[x][y]=cap;
		Cost[x][y]=z; Cost[y][x]=-z;
	}
	for (int i=1;i<=n;++i) nv[i]=A[i].size();
	fclose(fin);
}

bool BellmanFord()
{ int i,lq,j;
	for (i=1;i<=n;++i) 
	 {Dist[i]=oo; viz[i]=-1;}
	Dist[S]=0; 
	memset(inq,0,sizeof(inq));
	lq=1; Q[1]=S; inq[S]=true;
	for (i=1;i<=lq;++i)
	{
		int x=Q[i]; 
		for (j=0;j<nv[x];++j)
		{  int v=A[x][j]; 
		 if (C[x][v]-F[x][v]>0 && Dist[v]>Dist[x]+Cost[x][v])
			{ 
				Dist[v]=Dist[x]+Cost[x][v];
				viz[v]=x;
				if (!inq[v])
					{
						Q[++lq]=v;
						inq[v]=true;
					}
			}		
		}
		inq[x]=0;
	}
	
	if (Dist[D]!=oo) return true;
		return false;	
}

long long flux()
{
	long long fmcm=0;
	while (BellmanFord())
	{ int i;
		int fluxmin=oo;
		for (i=D; i!=S;i=viz[i])
		 fluxmin=min(fluxmin,C[viz[i]][i]-F[viz[i]][i]);
		for (i=D; i!=S; i=viz[i])
		{
		 F[viz[i]][i]+=fluxmin;
		 F[i][viz[i]]-=fluxmin;
		}	
		
		fmcm+=fluxmin*Dist[D];
	}	
	return fmcm;
}

void afisare(long long f)
{
	FILE *fout=fopen("fmcm.out","w");
	fprintf(fout,"%lld\n",f);
	fclose(fout);
}

int main()
{
	citire();
	afisare(flux());
	return 0;
}