[SCOI2007]修车_牛客博客

此题为2007年四川省选题目

前置知识

最小费用最大流
建议大家看这篇文章： https://baijiahao.baidu.com/s?id=1612179096991409044&wfr=spider&for=pc

思路

我们要使顾客的平均等待时间最小，即我们要使顾客的总等待时间最少
我们先考虑特殊情况，当m==1时，只有一位修车师傅
修第 $i$ 辆车耗时 $C_i$
若这i辆车按照 $1,2,3,4$ 顺序被修
那么等待的总时间： $cost=(C_1)+(C_1+C_2)+(C_1+C_2+C_3)...$

我们再考虑特殊情况,n==3

$cost=(C_1)+(C_1+C_2)+(C_1+C_2+C_3)$
整理一下式子

$cost=C_1*3+C_2*2+C_3*1$
可以看出，汽车先被修，对答案的贡献越大

我们再从特殊情况向回推
首先考虑n为任意值,m==1

$cost=C_1*n+C_2*(n-1)+C_3*(n-2)...$

再考虑m为任意值,n同时也为特殊值
这个时候我们就需要考虑汽车去哪个工人处维修
我用样例举例

2 2
3 2
1 4

我们每位位师傅拆成N个师傅，代表修第j辆车的师傅（注意，第j辆车是当前师傅修的第j辆车）
如下图
图片说明
红色的点为第一个师傅
绿色的点为第二个师傅
若第i辆车在第j个师傅修车的代价是k，第j个师傅分裂成n个点，车i向分裂的第p个点连代价为p*k的边，容量为1
源点向车连代价为0，容量为1的边
师傅向汇点连代价为0，容量为1的边
跑一遍最小费用最大流即可

为什么这样做是对的？
首先我们跑的是最大流，保证了每辆车都被维修
我们再单独看某个师傅修车
假设某个师傅只负责一俩车，如图
图片说明
那么车肯定回选择上面的点，因为代价回减少，即使我们的网络流先选择了下面的点，如果上面的点没选，那么此时就有一条增广路，车会重新选择上面的点
而且师傅向汇点连边的容量是1，保证了师傅每个步骤只修1辆车
由此可见，对于一个师傅的分裂点，肯定不会存在1，3点被利用，2号点不被利用的情况，因为1，2点被利用代价更优
我们再回头看我们最开始考虑的特殊情况，m==1时

$cost=C_1*n+C_2*(n-1)+C_3*(n-2)...$

不就正和这个师傅在网络流中得到的代价一样吗？
就此，我们可以得出，最小费用流跑出的答案就是我们顾客等待总时间的最小值
除以顾客总数，我们就可以得到顾客平均等待的时间最小值

参考代码

#include<bits/stdc++.h>
using namespace std;
const int inf=101010;
int m,n,S,T;
int c[20][70];
struct oppo{
    int to,s,w,nex;
}rod[1000006];
int head[100005],tot;
void add(int from,int to,int s,int w)
{
    rod[tot].to=to;
    rod[tot].s=s;
    rod[tot].nex=head[from];
    rod[tot].w=w;
    head[from]=tot++;
}
void link(int from,int to,int s,int w)
{
    add(from,to,s,w);
    add(to,from,0,-w);
}
bool flag[100005];
int d[100005];
int cur[100005];//当前弧优化 
bool spfa()
{
    queue<int> v;
    memset(d,10,sizeof(d));
    d[S]=0;cur[S]=head[S];v.push(S);
    while(v.size()){
        int lxl=v.front();
        v.pop();
        for(int i=head[lxl];~i;i=rod[i].nex){
            int to=rod[i].to;
            if(rod[i].s&&d[to]>d[lxl]+rod[i].w){
                d[to]=d[lxl]+rod[i].w;
                cur[to]=head[to];
                v.push(to);
            }
        }
    }
    return d[T]!=d[100000];
}
bool vis[100005];
int find(int x,int low)
{
    if(x==T) return low;
    vis[x]=1;
    int all=0;
    for(int i=cur[x];~i;i=rod[i].nex){
        cur[x]=i;
        int to=rod[i].to;
        if(rod[i].s&&d[to]==d[x]+rod[i].w&&!vis[to]){
            int t=find(to,min(rod[i].s,low-all));
            if(!t) d[to]=-1;
            rod[i].s-=t;
            rod[i^1].s+=t;
            all+=t;
        }
        if(all==low) break;
    }
    vis[x]=0;
    return all;
}
int dinic()
{
    int ans=0,r;
    while(spfa()) while(r=find(S,inf)) ans+=r*d[T];
    return ans;
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>m>>n;
    S=0,T=(m+1)*(n+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&c[j][i]);
    //建边
    for(int i=1;i<=n;i++){
        link(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++)
                link(i,j*n+k,1,c[j][i]*k);
        }    
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            link(i*n+j,T,1,0);
    printf("%.2lf",(double)dinic()/n);
    return 0;
}