记录编号	360730	评测结果	AAAAAAAAAA
题目名称	[SCOI 2007] 修车	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.334 s
提交时间	2016-12-31 15:41:05	内存使用	27.10 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1010,M=1e6+10;
struct edge{
	int f,t,g,l,o;
	edge(int F=0,int T=0,int G=0,int L=0,int O=0){
		f=F;t=T;g=G;l=L;o=O;
	}
}w[M];
int head[N],next[M],tail[N];
void add(int f,int t,int g,int l){
	static int cnt=0;
	cnt++;w[cnt]=edge(f,t,g,l,cnt+1);
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	cnt++;w[cnt]=edge(t,f,0,-l,cnt-1);
	if (!head[t]) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}
int n,m,f[N][N],s,t,ans,dis[N],flow[N],from[N];
bool inque[N];
queue<int> Q;
bool spfa(){
	for (int i=s;i<=t;i++) dis[i]=1e9;
	flow[s]=1e9;dis[s]=0;
	Q.push(s);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		inque[v]=0;
		for (int i=head[v];i;i=next[i])
		if (w[i].g&&dis[w[i].t]>dis[v]+w[i].l){
			dis[w[i].t]=dis[v]+w[i].l;
			flow[w[i].t]=min(flow[v],w[i].g);
			from[w[i].t]=i;
			if (!inque[w[i].t]) Q.push(w[i].t),inque[w[i].t]=1;
		}
	}
	if (dis[t]==1e9) return 0;
	int df=flow[t];ans+=dis[t]*df;
	for (int i=from[t];i;i=from[w[i].f])
		w[i].g-=df,w[w[i].o].g+=df;
	return 1;
}
int P(int x,int y){//第x个工人修倒数第y辆车 
	return (x-1)*n+y;
}
int main()
{
	freopen("scoi2007_repair.in","r",stdin);
	freopen("scoi2007_repair.out","w",stdout);
	scanf("%d%d",&m,&n);
	s=0;t=n*m+n+1;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++){
		scanf("%d",&f[i][j]);
		for (int k=1;k<=n;k++)
			add(n*m+i,P(j,k),1,k*f[i][j]);
	}
	for (int i=1;i<=n;i++) add(s,n*m+i,1,0);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
		add(P(j,i),t,1,0);
	while (spfa());
	printf("%.2lf\n",1.0*ans/n);
	return 0;
}