BZOJ_1070_[SCOI2007]修车

BZOJ_1070_[SCOI2007]修车_费用流

Description

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

Input

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

Output

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

Sample Input

2 2
3 2
1 4

Sample Output

1.50

HINT

数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)

对于1个技术人员p，假设他第i个修的车是第j辆车，对等待时间的贡献为(k-i)*t[j][p]其中k为安排这个人修车的数量。

考虑把每个技术人员拆成n个点，对于每辆车i，向这些点连一条容量1费用为时间k*t[i][j]，表示第j个人倒数第k个时间段修第i辆车。然后源点向每个车连容1费0，每个拆点后的技术人员向汇点连容1费0，然后跑最小费用最大流即可。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 850
#define M 250050
#define S (n*m+m+1)
#define T (n*m+m+2)
#define inf 0x3f3f3f3f
int head[N],to[M],nxt[M],flow[M],val[M],cnt=1,n,m,inq[N];
int t[70][70],dis[N],Q[N],l,r,path[N];
inline void add(int u,int v,int f,int w) {
    to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; flow[cnt]=f; val[cnt]=w;
    to[++cnt]=u; nxt[cnt]=head[v]; head[v]=cnt; flow[cnt]=0; val[cnt]=-w;
}
bool spfa() {
    memset(dis,0x3f,sizeof(dis));
    memset(path,0,sizeof(path));
    dis[S]=0; l=r=0; Q[r++]=S; inq[S]=1;
    int i;
    while(l!=r) {
        int x=Q[l++];if(l==n*m+m+1) l=0; inq[x]=0;
        for(i=head[x];i;i=nxt[i]) if(flow[i]&&dis[to[i]]>dis[x]+val[i]) {
            dis[to[i]]=dis[x]+val[i];
            path[to[i]]=i^1;
            if(!inq[to[i]]) {
                inq[to[i]]=1; Q[r++]=to[i]; if(r==n*m+m+1) r=0; 
            }
        }
    }
    return dis[T]<inf;
}
void mcmf() {
    int minc=0,maxf=0,i;
    while(spfa()) {
        int nf=1<<30;
        for(i=T;i!=S;i=to[path[i]]) {
            nf=min(nf,flow[path[i]^1]);
        }
        for(i=T;i!=S;i=to[path[i]]) {
            flow[path[i]]+=nf;
            flow[path[i]^1]-=nf;
            minc+=nf*val[path[i]^1];
        }
        maxf+=nf;
    }
    printf("%.2lf
",1.0*minc/m);
}
int main() {
    scanf("%d%d",&n,&m);
    int i,j,k;
    for(i=1;i<=m;i++) {
        for(j=1;j<=n;j++) {
            scanf("%d",&t[i][j]);
        }
    }
    for(i=1;i<=m;i++) {
        add(S,i,1,0);
        for(j=1;j<=n;j++) {
            for(k=1;k<=m;k++) {
                add(i,j*m+k,1,k*t[i][j]);
            }
        }
    }
    for(i=1;i<=n;i++) {
        for(j=1;j<=m;j++) {
            add(i*m+j,T,1,0);
        }
    }
    mcmf();
}