学步园

题意：有n个任务需要用m台机器来完成，给出了第i个任务在第j个机器上需要花的时间。但是，每台机器一次只能工作一个任务，因此有些任务如果非要在某台机器上运行可能需要等待。求任务需要时间的最小平均值。

思路：第一眼看到感觉就是网络流问题，但没想到如何表示一台机器完成多个任务的时间如何表示。起初想到用标记边访问的次数来表示，细想是错的。。。。

看了别人的想法，原来是用折点来表示。若某台机器按顺序执行k个任务，且k个任务的执行时间分别为t1,t2…tk,则k个任务的总的执行时间是t1*k+t2*(k-1)+t3*(k-2)+…+tk-1*2+tk。现在将机器拆点，拆成N个。第j个机器的第k个点表示该机器执行倒数第k个任务。连接该点的边的权值即为t[i][j]*k.以此构图后就可直接上模板了。

//5228K	938MS
#include <stdio.h>
#include <string.h>
const int inf = 0x3f3f3f3f;
const int VM = 50*50+60;
const int EM = (50*50*50+50+50*50)*2 + 10;

struct Edge
{
    int to,nxt,cap,cost,re;
} edge[EM];

int head[VM],pre[VM],vedge[EM];
int ep,src,des;

void addedge (int cu,int cv,int cw,int co)
{
    edge[ep].to = cv,edge[ep].cap = cw;
    edge[ep].cost = co,edge[ep].re = ep+1;
    edge[ep].nxt = head[cu],head[cu] = ep ++;

    edge[ep].to = cu,edge[ep].cap = 0;
    edge[ep].cost = -co,edge[ep].re = ep -1;
    edge[ep].nxt = head[cv],head[cv] = ep ++;
}

int spfa()
{
    int que[VM],vis[VM],dis[VM];
    int i,front = 0,rear = 0;
    memset (dis,0x3f,sizeof(dis));
    memset (vis,0,sizeof(vis));
    dis[src] = 0,que[rear++] = src;
    while (front != rear)
    {
        int u = que[front ++];
        front %= VM;
        vis[u] = 0;
        for (i = head[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if (edge[i].cap > 0&&dis[v]>dis[u]+edge[i].cost)
            {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if (!vis[v])
                {
                    que[rear++] = v;
                    rear %= VM;
                    vis[v] = 1;
                }
            }
        }
    }
    if (dis[des] == inf)
        return 0;
    return 1;
}
int MaxMatch()
{
    int res = 0;
    while (spfa())
    {
        int u,k;
        for (u = des; u != src; u = edge[edge[k].re].to)
        {
            k = pre[u];
            edge[k].cap -= 1;
            edge[edge[k].re].cap += 1;
            res += edge[k].cost;
        }
    }
    return res;
}
int main ()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    int T,n,m,i,j,cc;
    scanf ("%d",&T);
    while (T --)
    {
        scanf ("%d%d",&n,&m);
        memset (head,-1,sizeof(head));
        ep = 0,src = 0,des = n+m*n+1;
        for (i = 1; i <= n; i ++)
        {
            addedge (src,i,1,0);
            for (j = 1; j <= m; j ++)
            {
                scanf ("%d",&cc);
                for (int k = 1; k <= n; k ++)
                {
                    addedge (i,n+(j-1)*n+k,1,cc*k);
                    if(i == 1)
                        addedge (n+(j-1)*n+k,des,1,0);
                }
            }

        }
        int ans = MaxMatch();
        printf ("%.6lf\n",ans*1.0/n);
    }
    return 0;
}