费用流经典题目。

---

自我感觉跟很像。

利用费用提前计算的思想来建图就行了。

代码：

#include
    
     #define N 1005#define M 100005using namespace std;inline int read(){
    	int ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans;}int n,m;struct edge{
    int v,w,c,next;};struct MCMF{
    	edge e[M<<1];	int first[N],cnt,d[N],flow[N],pred[N],pos[N],q[N],hd,tl,s,t;	bool in[N];	inline void init(){
    s=0,t=n*m+n+1,memset(first,-1,sizeof(first)),cnt=-1;}	inline void addedge(int u,int v,int c,int w){
    e[++cnt].v=v,e[cnt].w=w,e[cnt].c=c,e[cnt].next=first[u],first[u]=cnt;}	inline void add(int u,int v,int c,int w){
    addedge(u,v,c,w),addedge(v,u,0,-w);}	inline bool spfa(){
    		queue
     
      q;		for(int i=1;i<=t;++i)d[i]=0x3f3f3f3f;		memset(in,false,sizeof(in)),d[s]=0,in[s]=1,pred[t]=-1,flow[s]=0x3f3f3f3f,q.push(s);		while(!q.empty()){
    			int x=q.front();			q.pop(),in[x]=0;			for(int i=first[x];~i;i=e[i].next){
    				int v=e[i].v;				if(!e[i].c||d[v]<=d[x]+e[i].w)continue;				d[v]=d[x]+e[i].w,pred[v]=x,pos[v]=i,flow[v]=min(flow[x],e[i].c);				if(!in[v])in[v]=1,q.push(v);			}		}		return d[t]!=0x3f3f3f3f;	}	inline void solve(){
    		int ans=0;		for(int w=t;spfa();w=t){
    			ans+=d[t];			while(w!=s)e[pos[w]].c-=flow[t],e[pos[w]^1].c+=flow[t],w=pred[w];		}		printf("%.2lf",(double)((double)ans)/((double)n));	}}mcmf;int main(){
    	m=read(),n=read(),mcmf.init();	for(int i=1;i<=n;++i)mcmf.add(mcmf.s,i+n*m,1,0);	for(int i=1;i<=n*m;++i)mcmf.add(i,mcmf.t,1,0);	for(int i=1,v;i<=n;++i){
    		for(int j=1;j<=m;++j){
    			v=read();			for(int k=1;k<=n;++k)mcmf.add(i+n*m,(j-1)*n+k,1,v*k);		}	}	mcmf.solve();	return 0;}