程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 10746 Crime Wave – The Sequel(費用流)

UVA 10746 Crime Wave – The Sequel(費用流)

編輯：C++入門知識

UVA 10746 Crime Wave – The Sequel(費用流)

ProblemG

CrimeWave – The Sequel

Input: StandardInput

Output: StandardOutput

TimeLimit: 2 Seconds

n bankshave been robbed this fine day. m (greater than orequal to n) police cruisers are on duty at variouslocations in the city. n of the cruisers should bedispatched, one to each of the banks, so as to minimize the averagetime of arrival at the n banks.

Input

Theinput file contains several sets of inputs. The description of eachset is given below:

Thefirst line of input contains 0 < n <= m <=20. n lines follow, each containing m positivereal numbers: the travel time for cruiser m to reachbank n.

Inputis terminated by a case where m=n=0. This case should notbe processed.

Output

Foreach set of input output a single number: the minimum average traveltime, accurate to 2 fractional digits.

SampleInput Outputfor Sample Input

3 4
10.0 23.0 30.0 40.0
5.0 20.0 10.0 60.0
18.0 20.0 20.0 30.0

13.33

Problemsetter: GordonCormack, EPS

題意：

有m個警察，派n個警察到n個銀行，給出每個警察到各銀行的時間，求最小的平均時間。

分析：

平均乘上n就是總時間，也就是要最小化總時間，那麼用費用流就可以解決問題。各銀行向每個警察連邊，容量1,費用為時間;增加源點，源點向各銀行連邊，容量1,費用0;增加匯點，警察向匯點連邊，容量1,費用0。在圖中跑費用流就行。

這題最惡心的地方在於保留小數，結果加上eps再輸出。這裡涉及到保留小數方法，是用傳統的四捨五入還是用銀行家捨入？都不知道以後涉及到小數的輸出要怎麼搞了，這種東西就該spj啊。

/*
 *
 *	Author	:	fcbruce
 *
 *	Date	:	2014-09-05 20:37:26 
 *
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#define sqr(x) ((x)*(x))
#define LL long long
#define itn int
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
#define eps 1e-10

#ifdef _WIN32
	#define lld %I64d
#else
	#define lld %lld
#endif

#define maxm 2333
#define maxn 64

using namespace std;

int fir[maxn];
int u[maxm],v[maxm],cap[maxm],flow[maxm],nex[maxm];
double cost[maxm];
int e_max;
double d[maxn];
int p[maxn];
bool inq[maxn];
int q[maxm<<3];

inline void add_edge(int _u,int _v,int _cap,double _cost)
{
	int e;
	e=e_max++;
	u[e]=_u;v[e]=_v;cap[e]=_cap;cost[e]=_cost;
	nex[e]=fir[u[e]];fir[u[e]]=e;
	e=e_max++;
	u[e]=_v;v[e]=_u;cap[e]=0;cost[e]=-_cost;
	nex[e]=fir[u[e]];fir[u[e]]=e;
}

void SPFA(int s)
{
	memset(inq,0,sizeof inq);
	memset(d,0x7f,sizeof d);
	int f,r;
	d[s]=0;
	q[f=r=0]=s;
	while (f<=r)
	{
		int x=q[f++];
		inq[x]=false;
		for (int e=fir[x];~e;e=nex[e])
		{
			if (cap[e]>flow[e] && d[v[e]]>d[u[e]]+cost[e]+eps)
			{
				d[v[e]]=d[u[e]]+cost[e];
				p[v[e]]=e;
				if (!inq[v[e]])
				{
					inq[v[e]]=true;
					q[++r]=v[e];
				}
			}
		}
	}
}

pair min_cost_flow(int s,int t)
{
	memset(flow,0,sizeof flow);
	double total_cost=0;
	int total_flow=0;
	
	for (;;)
	{
		SPFA(s);
		
		if (d[t]>INF)	break;
		
		int _f=INF;
		for (int e=p[t];;e=p[u[e]])
		{
			_f=min(_f,cap[e]-flow[e]);
			if (u[e]==s)	break;
		}
		
		for (int e=p[t];;e=p[u[e]])
		{
			flow[e]+=_f;
			flow[e^1]-=_f;
			if (u[e]==s)	break;
		}
		
		total_cost+=d[t]*_f;
		total_flow+=_f;
	}
	
	return make_pair(total_cost,total_flow);
}

int main()
{
#ifdef FCBRUCE
	freopen(/home/fcbruce/code/t,r,stdin);
#endif // FCBRUCE
	
	int n,m;
	
	while (scanf( %d%d,&n,&m),n||m)
	{
		int s=0,t=n+m+1;
		
		e_max=0;
		memset(fir,-1,sizeof fir);
		
		double w;
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=m;j++)
			{
				scanf( %lf,&w);
				add_edge(i,n+j,1,w);
			}
		}
		
		for (int i=1;i<=n;i++)
			add_edge(s,i,1,0);
		
		for (int j=1;j<=m;j++)
			add_edge(j+n,t,1,0);
		
		auto res=min_cost_flow(s,t);
		
		printf( %.2f
,res.first/res.second+eps);
	}
	
	return 0;
}