BZOJ_1070.cpp

#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=610;
const int MAXM=80000;
const int inf=1e9;

struct Edge {
	int u, v, flow, cost;
	int next;
	Edge(){}
	Edge(int u, int v, int f, int c, int n):u(u), v(v), flow(f), cost(c), next(n){}
}E[MAXM];

bool vis[MAXN];
int head[MAXN];
int pre[MAXN], dis[MAXN];
int N, S, T, ans, cnt;

void addedge(int u, int v, int f, int c) {
	E[cnt]=Edge(u, v, f, c, head[u]); head[u]=cnt++;
	E[cnt]=Edge(v, u, 0, -c, head[v]); head[v]=cnt++;
}

bool spfa()
{
	queue<int>q; while (!q.empty()) q.pop();
	for (int i=0; i<=T; i++) dis[i]=inf, vis[i]=0, pre[i]=-1;
	q.push(S); vis[S]=1; dis[S]=0;
	while (!q.empty()) {
		int u=q.front(), v; q.pop(); vis[u]=false;
		for (int now=head[u]; now!=-1; now=E[now].next)
			if (dis[v=E[now].v]>dis[u]+E[now].cost && E[now].flow>0) {
				dis[v]=dis[u]+E[now].cost; pre[v]=now;
				if (!vis[v]) q.push(v), vis[v]=true;
			}
	}
	return (dis[T]<inf);
}

int MCMF()
{
    int mincost=0, maxflow=0;
    while (spfa()) {
		int nec=inf;
		for (int now=pre[T]; now!=-1; now=pre[E[now].u]) nec=min(nec, E[now].flow);
		mincost+=nec*dis[T]; maxflow+=nec;
		for (int now=pre[T]; now!=-1; now=pre[E[now].u]) {
			E[now].flow-=nec; E[now^1].flow+=nec;
		}
	}
	return mincost;
}

int main() {
	static int a[100][10];
	int n, m;
	scanf("%d%d", &m, &n);
	S=0; T=n+n*m+1; cnt=0;
	memset(head, -1, sizeof(head));
	for (int i=1; i<=n; i++) {
		addedge(S, i, 1, 0);
		for (int j=1; j<=m; j++) {
			scanf("%d", &a[i][j]);
			for (int k=1; k<=n; k++) addedge(i, j*n+k, 1, k*a[i][j]);
		}
	}
	for (int i=1; i<=m; i++)
		for (int j=1; j<=n; j++)
			addedge(i*n+j, T, 1, 0);
	int ans=MCMF();
	printf("%.2f\n", (double)ans/n);
	return 0;
}