学步园

 题目链接：点击打开链接

【题意】

有N个订单和M个机器，给出第i个订单在第j个机器完成的时间Mij，每台机器同一时刻只能处理一个订单，机器必须完整地完成一个订单后才能接着完成下一个订单。问N个订单完成时间的平均值最少为多少。

【解答】

       假设某个机器处理了k个玩具,那么对于这些玩具，有两种时间，一种是真正处理的时间，一种是等待的时间，等待的时间就是之前所有处理的玩具的时间，

       假设这k个玩具真正用在加工的时间分为a1,a2,a3...ak, 那么每个玩具实际的时间是加工的时间+等待时间，分别为

a1, a1+a2, a1+a2+a3.......a1+a2+...ak。

       求和之后变为 a1 *k + a2 * (k - 1) + a3 * (k - 2).... + ak

       这时就发现，每个玩具之间的实际时间可以分开来算 然后求和了。

       因为对每个机器，最多可以处理n个玩具，所以可以拆成n个点，1~n分别代表某个玩具在这个机器上倒数第几个被加工的， 所以我们对于每个玩具i，机器j中拆的每个点k，连接一条z[i][j]*k权值的边。

      建图：建立源汇点，源点和每个订单流量为1，费用为0；订单和每台机器拆成的点k建立流量为1，费用为Mij*k；

k与汇点建立流量为1，费用为0，求最小费用最大流即可。神吧这建图模型。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>

using namespace std;
const int N=4200;
const int MAXE=535000;
const int inf=1<<30;
int  head[N],s,t,cnt,n,m;
int  flow=0,ans=0;
int  d[N];
int  pre[N];
bool vis[N];
int q[MAXE+79000]; 

struct Edge
{
    int u,v,next;
    int c,w;
}edge[MAXE];

void addedge(int u,int v,int c,int  w)
{
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].c=c;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].v=u;
    edge[cnt].u=v;
    edge[cnt].w=-w;
    edge[cnt].c=0;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}

int SPFA()
{
    for(int i=0;i<=t;i++)
        d[i]=inf;
    memset(pre,-1,sizeof(pre));
    memset(vis,0,sizeof(vis));
    d[s]=0;
    int l=0,r=0;
    q[r++]=s;
    vis[s]=1;
    while(l<=r)
    {
        int u=q[l++];
        vis[u]=0;
        for(int j=head[u];j!=-1;j=edge[j].next)
        {
            int v=edge[j].v;
            if(edge[j].c>0&&d[u]+edge[j].w<d[v])
            {
                d[v]=d[u]+edge[j].w;
                pre[v]=j;
                if(!vis[v])
                {
                    vis[v]=1;
                    q[r++]=v;
                }
            }
        }
    }
    if(d[t]==inf)
        return 0;
    return 1;
}

void MCMF()
{
    flow=0;
    while(SPFA())
    {
        ans+=d[t];
        int u=t;
        int mini=inf;
        while(u!=s)
        {
            if(edge[pre[u]].c<mini)
                mini=edge[pre[u]].c;
                u=edge[pre[u]].u;
        }
        flow+=mini;
        u=t;
        while(u!=s)
        {
            edge[pre[u]].c-=mini;
            edge[pre[u]^1].c+=mini;
            u=edge[pre[u]].u;
        }
    }
}

int mp[160][160];

int main()
{
 int cas;
 scanf("%d",&cas);
 while(cas--)
 {
    scanf("%d%d",&n,&m);
    s=0;
    ans=0;
    flow=0;
    t=n+n*m+1;
    memset(head,-1,sizeof(head));
    cnt=0;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        scanf("%d",&mp[i][j]);
    for(int i=1;i<=n;i++)
     addedge(s,i,1,0);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
       for(int k=1;k<=n;k++)
        {
            addedge(i,n+(j-1)*n+k,1,mp[i][j]*k);
        }
    for(int i=1;i<=m;i++)
     for(int j=1;j<=n;j++)
     {
         addedge(n+(i-1)*n+j,t,1,0);
     }
     MCMF();
     printf("%.6lf\n",ans*1.0/n);
 }
 return 0;
}