【BZOJ1070】【SCOI2007】修车

    裸的最小费用最大流。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=80,maxm=20,maxv=maxn*maxm,inf=~0U>>1;

int head[maxv],next[maxv*maxn<<1],E[maxv*maxn<<1],F[maxv*maxn<<1],C[maxv*maxn<<1],Ecnt;
int cost[maxm][maxn];
int dis[maxv];
int n,m,s,t;

void Add_Edge(int x,int y,int flow,int c) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;F[Ecnt]=0;C[Ecnt]=c;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;F[Ecnt]=flow;C[Ecnt]=-c;}

int q[maxv],vis[maxv],qhead,qtail;
bool Spfa()
{
	memset(dis,0x7F,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[t]=0;
	qhead=0;qtail=1;
	q[0]=t;vis[t]=1;
	while (qhead!=qtail)
	{
		int x=q[qhead++];
		if (qhead==maxv) qhead=0;
		vis[x]=0;
		for (int i=head[x];i;i=next[i]) if (dis[E[i]]>dis[x]-C[i] && F[i])
		{
			dis[E[i]]=dis[x]-C[i];
			if (!vis[E[i]]) {q[qtail++]=E[i];vis[E[i]]=1;if (qtail==maxv) qtail=0;}
		}
	}
	return dis[s]!=0x7F7F7F7F;
}

int DFS(int x,int flow,int &res)
{
	vis[x]=1;
	if (x==t) return flow;
	int rest=flow;
	for (int i=head[x];i && rest;i=next[i]) if (dis[E[i]]==dis[x]-C[i] && F[i^1] && !vis[E[i]])
	{
		int d=DFS(E[i],min(rest,F[i^1]),res);
		res+=d*C[i];
		rest-=d;F[i]+=d;F[i^1]-=d;
	}
	return flow-rest;
}

int MinCostFlow()
{
	int res=0;
	while (Spfa())
	{
		vis[t]=1;
		while (vis[t])
		{
			memset(vis,0,sizeof(vis));
			DFS(s,inf,res);
		}
	}
	return res;
}

int main()
{
	scanf("%d%d",&m,&n);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
		scanf("%d",&cost[j][i]);
	s=n*m+n+1;t=s+1;Ecnt=1;
	for (int i=1;i<=n;i++)
		Add_Edge(s,n*m+i,1,0);
	for (int i=1;i<=n*m;i++)
		Add_Edge(i,t,1,0);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	for (int k=1;k<=n;k++)
		Add_Edge(n*m+i,(j-1)*n+k,1,cost[j][i]*k);
	printf("%.2f\n",(double)MinCostFlow()/n);
	return 0;
}