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;

}