C++(g++ 7.5.0) 解法, 执行用时: 182ms, 内存消耗: 1496K, 提交时间: 2022-09-03 11:02:52

#include<bits/stdc++.h>
using namespace std ;
const int N = 10005, M = 200005, INF = 1<<30 ;
struct Edge
{
    int nxt,to,c,cost ;
}e[M] ;
int head[N],d[N],tot=1 ;
int S,T ;
queue<int>q ;
bool inq[N],vis[N] ;
void add(int from,int to,int c,int cost)
{
    e[++tot].to=to ; e[tot].c=c ; e[tot].cost=cost ; e[tot].nxt=head[from] ; head[from]=tot ;
    e[++tot].to=from ; e[tot].c=0 ; e[tot].cost=-cost ;  e[tot].nxt=head[to] ; head[to]=tot ;
}
bool spfa()
{
    while(!q.empty()) q.pop() ;
    for(int i=1;i<=T;++i) d[i]=INF,inq[i]=vis[i]=0 ;
    q.push(S) ; d[S]=0 ; inq[S]=1 ;
    while(!q.empty())
    {
        int x=q.front() ; q.pop() ; inq[x]=0 ;
        for(int i=head[x];i;i=e[i].nxt)
        {
            if(!e[i].c) continue ;
            int y=e[i].to ;
            if(d[y]>d[x]+e[i].cost)
            {
                d[y]=d[x]+e[i].cost ;
                if(!inq[y]) q.push(y),inq[y]=1 ;
            }
        }
    }
    return d[T]<INF ;
}
int maxflow=0,ans=0 ;
// maxflow -> 最大流
// ans -> 最小费用
int dinic(int x,int flow)
{
    if(x==T)
    {
        maxflow+=flow ;
        ans+=flow*d[T] ;
        return flow ;
    }
    vis[x]=1 ;
    int rest=flow,k ;
    for(int i=head[x];i;i=e[i].nxt)
    {
        if(!e[i].c||vis[e[i].to]) continue ;
        int y=e[i].to ;
        if(d[y]==d[x]+e[i].cost)
        {
            k=dinic(y,min(e[i].c,rest)) ;
            e[i].c-=k ; e[i^1].c+=k ; rest-=k ;
            if(!rest) break ;
        }
    }
    return flow-rest ;
}
//main
int n,m ;
int a[65][10] ;
void solve()
{
    tot=1 ; memset(head,0,sizeof(head)) ;
    ans=maxflow=0 ;
    cin>>m>>n ;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;j++)
            cin>>a[i][j] ;
    S=n+m*n+1 ; T=S+1 ;
    for(int i=1;i<=n;++i)
    {
        add(S,i,1,0) ;
        for(int j=1;j<=m;j++)
            for(int k=1;k<=n;++k)
                add(i,n+j+(k-1)*m,1,a[i][j]*k) ;
    }
    for(int i=1;i<=m;++i)
        for(int k=1;k<=n;++k)
            add(n+i+(k-1)*m,T,1,0) ;
    while(spfa()) dinic(S,INF) ;
    printf("%.2lf\n",(double)ans/n) ;
}
int main()
{
    int T ; T=1 ;
    while(T--) solve() ;
    return 0 ;
}

C++(clang++ 11.0.1) 解法, 执行用时: 138ms, 内存消耗: 2780K, 提交时间: 2023-01-02 14:48:06

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int M = 5e6 + 10, INF = 1e8;
int h[10010], e[M], ne[M], f[M], w[M], idx, d[10010], incf[10010], n, m, S, T, pre[10010];
bool st[10010];
void add(int a, int b, int c, int d)
{
	e[idx] = b, ne[idx] = h[a], f[idx] = c, w[idx] = d, h[a] = idx ++;
	e[idx] = a, ne[idx] = h[b], f[idx] = 0, w[idx] = -d, h[b] = idx ++;
}

bool spfa()
{
	queue<int>q;
	memset(d, 0x3f, sizeof d);
	memset(incf, 0, sizeof incf);
	d[S] = 0;
	incf[S] = INF;
	q.push(S);

	while(!q.empty())
	{
		auto t = q.front();
		q.pop();
		st[t] = false;
		for(int i = h[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if(d[j] > d[t] + w[i] && f[i])
			{
				d[j] = d[t] + w[i];
				pre[j] = i;
				incf[j] = min(incf[t], f[i]);
				if(!st[j])
				{
					st[j] = 1;
					q.push(j);
				}
			}
		}
	}
	return incf[T] > 0;
}	

int EK()
{
	int flow = 0, cost = 0;
	while(spfa())
	{
		flow += incf[T];
		cost += incf[T] * d[T];
		for(int i = T; i != S; i = e[pre[i] ^ 1])
		{
			f[pre[i]] -= incf[T];
			f[pre[i] ^ 1] += incf[T];
		}
	}
	return cost;
}
typedef pair<int, int>PII;
int a[110][100];

int get(int x, int y)
{
	return (x - 1) * n + y;
}
signed main()
{
	cin >> m >> n;

	memset(h, -1, sizeof h);
	for(int i = 1; i <= n; i ++ )
		for(int j = 1; j <= m; j ++ ) cin >> a[j][i];

	S = 0, T = n * m + n + 1;

	for(int i = 1; i <= m; i ++ )
		for(int j = 1; j <= n; j ++ )
		{
			add(S, get(i, j), 1, 0);
			for(int k = 1; k <= n; k ++ ) add(get(i, j), n * m + k, 1, j * a[i][k]);
		}
	for(int i = 1; i <= n; i ++ ) add(n * m + i, T, 1, 0);

	cout << fixed << setprecision(2) << (EK() + 0.0) / n << '\n';
}