[BZOJ1070]&&[SCOI2007] 修车

描述 Description

同一时刻有 N 位车主带着他们的爱车来到了汽车维修中心。维修中心共有 M 位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这 M 位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。 说明:顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

输入格式 InputFormat

第一行有两个 m,n,表示技术人员数与顾客数。 接下来 n 行,每行 m 个整数。第 i+1 行第 j 个数表示第 j 位技术人员维修第 i 辆车需要用的时间 T。

输出格式 OutputFormat

最小平均等待时间,答案精确到小数点后 2 位。

样例输入 SampleInput

2 2
3 2
1 4

样例输出 SampleOutput

1.50


BZOJ 1070


顾客与源点连边流量一费用零,每个技术人员拆成 n 个点其中第 i 个点表示该技术人员维修的倒数第 i 辆车然后每个点与每辆车连边流量一费用所花时间乘以剩余车辆数(即该车维修时间加上其他车辆的等待时间),再连边汇点流量一费用零跑 MCMF。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int inf=0x7fffffff/27.11;
const int maxn=605;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
    int to,fl,co,nx;
}e[maxn*maxn];
int head[maxn],dis[maxn],used[maxn],pre[maxn],flow[maxn];
int a[maxn][maxn];
int cnt,num,s;
deque <int> q;
inline void ins(int u,int v,int f,int c)
{
    e[cnt++]=(edge){v,f,c,head[u]};head[u]=cnt-1;
    e[cnt++]=(edge){u,0,-c,head[v]};head[v]=cnt-1;
}
inline bool spfa(int s,int t,int tim)
{
    int i,j,u,v,w;
    while (!q.empty()) q.pop_front();
    for (i=s;i<=t;i++) dis[i]=inf;
    pre[s]=-1;flow[s]=inf;
    q.push_back(s);used[s]=tim;dis[s]=0;
    while (!q.empty())
    {
        u=q.front();q.pop_front();used[u]--;
        for (i=head[u];i!=-1;i=e[i].nx)
        {
            v=e[i].to;
            if (dis[v]>dis[u]+e[i].co && e[i].fl>0)
            {
                dis[v]=dis[u]+e[i].co;
                flow[v]=min(flow[u],e[i].fl);
                pre[v]=i;
                if (used[v]!=tim)
                {
                    used[v]=tim;
                    if (!q.empty() && dis[v]<dis[q.front()]) q.push_front(v);
                    else q.push_back(v);
                }
            }
        }
    }
    return (dis[t]!=inf);
}
inline void mcmf(int s,int t)
{
    int i,j,ans=0;
    while (spfa(s,t,++num))
    {
        ans+=flow[t]*dis[t];
        for (i=pre[t];i!=-1;i=pre[e[i^1].to]) e[i].fl-=flow[t],e[i^1].fl+=flow[t];
    }
    printf("%.2lf\n",(double)ans/n);
}
int main()
{
    cnt=num=0;
    memset(head,-1,sizeof(head));
    scanf("%d%d",&m,&n);
    for (i=1;i<=n;i++) for (j=1;j<=m;j++) scanf("%d",&a[i][j]);
    s=0;t=n+m*n+1;
    for (i=1;i<=n;i++)
    {
        ins(s,i,1,0);
        for (j=1;j<=m;j++) for (k=1;k<=n;k++) ins(i,j*n+k,1,k*a[i][j]);
    }
    for (i=1;i<=m;i++) for (j=1;j<=n;j++) ins(i*n+j,t,1,0);
    mcmf(s,t);
    return 0;
}