Description:

$N$ 个人修 $M$ 辆车，不同的人修不同车花费的时间不同，求每个人修的车和修车的顺序，能得到的最短平均等待时间。

$2\le N \le 9$ $1\le M \le 60$

Solution:

当总等待时间最短时，平均等待时间最短，从原点向每一辆车连容量 $1$ 费用 $0$ 的边，将人拆成 $N$ 个点 $(i,1)$ ~ $(i,N)$ ，表示第 $i$ 个人的第 $j$ 次维修，从第 $i$ 辆车向 $(j,k)$ 连容量为 $1$ ，费用为 $k\times tim[i][j]$ 的边，表示第 $k$ 个修这辆车需要等待 $k\times tim[i][j]$ 的时间，跑最小费用最大流即可。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXM 11

#define MAXN 62

#define MAXP MAXN + MAXN * MAXM + 3

#define INF 0x3f3f3f3f

int to(int i,int j){return (i - 1) * m + j;}

int s,t;

int tim[MAXN][MAXM];

struct edge

{

	int to,nxt,c,f;

}e[(MAXN * MAXM * MAXN + MAXN + MAXN * MAXM) * 2];

int edgenum = 0;

int lin[MAXP];

void add(int a,int b,int c,int d)

{

	e[edgenum].to = b;e[edgenum].f = d;e[edgenum].nxt = lin[a];lin[a] = edgenum;e[edgenum].c = c;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;e[edgenum].c = -c;++edgenum;

	return;

}

int d[MAXP],pre[MAXP],rate[MAXP];

bool v[MAXP];

bool SPFA()

{

	memset(d,0x3f,sizeof(d));

	memset(pre,0,sizeof(pre));

	memset(v,false,sizeof(v));

	memset(rate,0x3f,sizeof(rate));

	queue<int> q;

	q.push(s);

	d[s] = 0;

	v[s] = true;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		v[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].c && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].c;

				rate[e[i].to] = min(rate[k],e[i].f);

				pre[e[i].to] = i;

				if(!v[e[i].to])

				{

					q.push(e[i].to);

					v[e[i].to] = true;

				}

			}

		}

	}

	return (d[t] != INF);

}

long long flow()

{

	for(int i = t;i != s;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].f -= rate[t];

		e[pre[i] ^ 1].f += rate[t];

	}

	return rate[t] * d[t];

}

long long EK()

{

	long long ans = 0;

	while(SPFA())ans += flow();

	return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d",&m,&n);

	s = n * m + n + 1;t = s + 1;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			scanf("%d",&tim[i][j]);

			for(int k = 1;k <= n;++k)

			{

				add(i,to(k,j) + n,tim[i][j] * k,1);

			}

		}

	}

	for(int i = 1;i <= n;++i)

	{

		add(s,i,0,1);

	}

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			add(to(i,j) + n,t,0,1);

		}

	}

	printf("%.2f\n",(double)EK() / (double)n);

	return 0;

}