Description
同一时刻有\(N\)位车主带着他们的爱车来到了汽车维修中心。维修中心共有\(M\)位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这\(M\)位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
Input
第一行有两个\(m,n\)，表示技术人员数与顾客数。 接下来\(n\)行，每行\(m\)个整数。第\(i+1\)行第\(j\)个数表示第\(j\)位技术人员维修第\(i\)辆车需要用的时间\(T_{j,i}\)。
Output
最小平均等待时间，答案精确到小数点后\(2\)位。
Sample Input
2 2
3 2
1 4
Sample Output
1.50
HINT
\((2 \le M \le 9,1 \le N \le 60), (1 \le T \le 1000)\)
这是一道比较明显的费用流题目。
这题构图很巧妙：
将每个工人拆成\(n\)个点，设第\(i\)个工人拆成的第\(j\)个点为\(P_{i,j}\)，\(P_{i,j}\)表示第\(i\)个人倒数第\(j\)个修的车是哪一辆。
\(P_{i,j}\)向第\(k\)辆车连接一条容量为\(1\)，费用为\(T_{i,k} \times j\)的边。
接着就是连接源汇点，最后跑最大费用最大流即可。
正确性也很明显。每个工人修的车只可以对它后面修的产生代价，而代价正好就是它的倒数名次与其时间的乘积。
zkw费用流是蒯的hzwer的，应该可以敲spfa吧。
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cstring>
using namespace std;
#define inf 0x7fffffff
#define T 601
using namespace std;
int n,m,cnt = 1,ans,t[61][10];
int d[605],q[605],from[605],head[605];
bool mark[605];
struct edge{int from,to,next,c,v;}e[100001];
inline int small(int a,int b) {if (a < b) return a; return b;}
void ins(int u,int v,int w,int c)
{
cnt++;
e[cnt].from = u; e[cnt].to = v;
e[cnt].next = head[u]; head[u] = cnt;
e[cnt].c = c; e[cnt].v = w;
}
void insert(int u,int v,int w,int c)
{
ins(u,v,w,c); ins(v,u,0,-c);
}
bool spfa()
{
memset(mark,0,sizeof(mark));
memset(d,0x7,sizeof(d));
d[T] = 0; mark[T] = 1;
queue <int> team;
team.push(T);
while (!team.empty())
{
int now = team.front();
team.pop();
for (int i = head[now];i;i = e[i].next)
if (e[i^1].v&&d[e[i].to] > d[now]-e[i].c)
{
d[e[i].to] = d[now]-e[i].c;
if (!mark[e[i].to])
{
mark[e[i].to] = true;
team.push(e[i].to);
}
}
mark[now] = false;
}
if (d[0] > 10000000) return false;
return true;
}
int dfs(int x,int f)
{
if (x == T)
{
mark[T] = 1;
return f;
}
int used = 0,w;
mark[x] = true;
for (int i = head[x];i;i = e[i].next)
if (!mark[e[i].to]&&e[i].v&&d[x]-e[i].c==d[e[i].to])
{
w = f - used;
w = dfs(e[i].to,small(e[i].v,w));
ans += w*e[i].c;
e[i].v -= w;
e[i^1].v += w;
used += w;
if (used == f) return f;
}
return used;
}
void zkw()
{
while (spfa())
{
mark[T] = 1;
while (mark[T])
{
memset(mark,0,sizeof(mark));
dfs(0,inf);
}
}
}
int main()
{
freopen("1070.in","r",stdin);
freopen("1070.out","w",stdout);
int i,j,k;
scanf("%d %d",&n,&m);
for (i = 1;i<=m;i++)
for (j = 1;j<=n;j++)
scanf("%d",t[i]+j);
for (i = 1;i<=n*m;i++)
insert(0,i,1,0);
for (int i = n*m+1;i<=n*m+m;i++)
insert(i,T,1,0);
for (i = 1;i<=n;i++)
for (j = 1;j<=m;j++)
for (k = 1;k<=m;k++)
insert((i-1)*m+j,n*m+k,1,t[k][i]*j);
zkw();
printf("%.2lf",(double)ans/m);
return 0;
}