记录编号	412387	评测结果	AAAAAAAAAA
题目名称	[SCOI 2007] 修车	最终得分	100
用户昵称	LadyLex	是否通过	通过
代码语言	C++	运行时间	0.479 s
提交时间	2017-06-09 08:15:25	内存使用	2.27 MiB

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int M=60;
const int N=70;
const int inf=0x7fffffff;
int n,m,val[N][N];
struct node{int qi,zhong,val,flow,next;}s[20*N*N];
int adj[M*N+4*N],e=1;
inline int min(int a,int b){return a<b?a:b;}
inline void add(int qi,int zhong,int val,int flow)
{
	s[++e].qi=qi;s[e].zhong=zhong;
	s[e].val=val;s[e].flow=flow;
	s[e].next=adj[qi];adj[qi]=e;
}
inline void fan_add(int qi,int zhong,int val,int flow)
{
	s[++e].qi=qi;s[e].zhong=zhong;
	s[e].val=val;s[e].flow=0;
	s[e].next=adj[qi];adj[qi]=e;
}
const int S=M*N+N+1;
const int T=M*N+N+2;
bool vis[M*N+4*N];
int a[M*N+4*N],p[M*N+4*N],ans,dis[M*N+4*N];
queue<int>q;
inline bool spfa()
{
	memset(vis,0,sizeof(vis));
	memset(dis,0x7f,sizeof(dis));
	memset(p,0,sizeof(p));
	int tmp=dis[1];a[S]=inf;
	dis[S]=0;vis[S]=1;p[S]=0;q.push(S);
	while(!q.empty())
	{
		int rt=q.front();vis[rt]=0;q.pop();
		for(int i=adj[rt];i;i=s[i].next)
		{
			int u=s[i].zhong;
			if(s[i].flow&&dis[u]>dis[rt]+s[i].val)
			{
				dis[u]=dis[rt]+s[i].val;p[u]=i;
				a[u]=min(a[rt],s[i].flow);
				if(!vis[u]){q.push(u);vis[u]=1;}
			}
		}
	}
	//printf("\n%d\n",dis[T]);
	if(dis[T]==tmp)return 0;
	ans+=dis[T];
	int u=T;
	while(u!=S)
	{
		//printf("%d ",u);
		s[p[u]].flow-=a[T];
		s[p[u]^1].flow+=a[T];
		u=s[p[u]].qi;
	}
	return 1;
}
int main()
{
	//freopen("Lex.txt","r",stdin);
	freopen("scoi2007_repair.in","r",stdin);
	freopen("scoi2007_repair.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&val[i][j]);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			add(i+j*n,T,0,1),fan_add(T,i+j*n,0,0);
	for(int j=1;j<=n;j++)
		add(S,j,0,1),fan_add(j,S,0,0);
	for(int j=1;j<=n;j++)
		for(int i=1;i<=m;i++)
			for(int k=1;k<=n;k++)
				add(j,i+k*n,val[j][i]*k,1),fan_add(i+k*n,j,-val[j][i]*k,0);
	while(spfa());
	printf("%.2lf",(ans*1.0)/n);
}