BZOJ 1070 修车

题目大意

给你一些人和一些车，人修车，每个人修每辆车的时间不同，每个人同时只能修理一台车。问最终的所有人的等待总时长的平均值的最小值。

拆点+费用流，第一次做这种套路的题。

平均值当然可以忽略，变成求总时长的最小值。

考虑对车进行贡献的计算。

第$i$个人修倒数第$j$辆车的总时间为$j*f[k][i]$（我就是在这里ik搞反了WA了一次= =）

所以将一个人拆成车数量个点，之后S连车，车连人(的车数量个点)，人连T，跑一边最小费用最大流就OK了。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10010
#define M 500000
int m,n,t[100][10],S=0,T=4999,dis[N],pre[N],frm[N],ans;
int to[M],nxt[M],val[M],cst[M],head[N],tot=1;
queue<int>q;
inline void AE(int x,int y,int a,int b)
{
	to[++tot]=y,nxt[tot]=head[x],head[x]=tot,val[tot]=a,cst[tot]=b;
	to[++tot]=x,nxt[tot]=head[y],head[y]=tot,val[tot]=0,cst[tot]=-b;
}
bool SPFA()
{
	q.push(S);
	memset(dis,0x3f,sizeof dis),dis[S]=0;
	while(!q.empty())
	{
		int pos=q.front();q.pop();
		for(int i=head[pos];i;i=nxt[i])
			if(val[i]&&dis[to[i]]>dis[pos]+cst[i])
			{
				dis[to[i]]=dis[pos]+cst[i];
				frm[to[i]]=pos,pre[to[i]]=i;
				q.push(to[i]);
			}
	}
	return dis[T]!=0x3f3f3f3f;
}
int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			scanf("%d",&t[i][j]);
	for(int i=1;i<=n;++i) AE(S,i,1,0);
	int tmp=n;
	for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j)
		{
			++tmp;
			for(int k=1;k<=n;++k) AE(k,tmp,1,j*t[k][i]);
			AE(tmp,T,1,0);
		}
	while(SPFA())
	{
		ans+=dis[T];
		for(int i=T;i!=S;i=frm[i]) val[pre[i]]--,val[pre[i]^1]++;
	}
	printf("%.2lf",1.0*ans/n);
	return 0;
}