P2053 [SCOI2007]修车

题目描述

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

说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

输入输出格式

输入格式：

第一行有两个数M,N，表示技术人员数与顾客数。

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

输出格式：

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

说明

\(2<=M<=9,1<=N<=60,1<=T<=1000\)

---

感觉费用流建模好难啊，也许是接触的少了？

我们发现每个车要把前面修车的都等一遍，也就是说如果某个技术人员连续修理\(c_1,c_2,..,c_n\)这些车，等待的总时间其实是\(w_1*n+w_2*(n-1)+...+w_n*1\)

我们可以把这些项分开处理。把每个修车的拆成车那么多个点，表示这个修车的在第几位给这个车子修车。

可以把车和新的修车的点看成两个集合，即是二分图带权匹配。

连边

1.S连每个车，容1费0

2.每个车连修车的点集，容1费层数*原始修车费用

3.修车的点连T，容1费0

还有一点，这样为什么保证了对于某个修车的\(j\)跑了第\(i\)层的点时前\(i-1\)层的点都跑过了呢？因为边权是正的跑最小费用最大流的时候贪心就一定先把费用比较小的跑掉了

---

Code：

#include <cstdio>

#include <queue>

#include <cstring>

const int N=802;

const int M=80010;

const int inf=0x3f3f3f3f;

int head[N],to[M],Next[M],edge[M],cost[M],cnt=1;

void add(int u,int v,int w,int c)

{

    to[++cnt]=v;edge[cnt]=w;cost[cnt]=c;Next[cnt]=head[u];head[u]=cnt;

    to[++cnt]=u;edge[cnt]=0;cost[cnt]=-c;Next[cnt]=head[v];head[v]=cnt;

}

int t,n,m;

void init()

{

    scanf("%d%d",&m,&n);//技术人员，车子数量

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=m;j++)

        {

            scanf("%d",&t);

            for(int k=1;k<=n;k++)

                add(i,n+(k-1)*m+j,1,t*k);

        }

        add(0,i,1,0);

    }

    t=n+n*m+1;

    for(int j=1;j<=m;j++)

        for(int k=1;k<=n;k++)

            add(n+(k-1)*m+j,t,1,0);

}

int dep[N],dis[N],used[N],pre[N],ans;

bool spfa()

{

    memset(dis,0x3f,sizeof(dis));

    dis[0]=0;

    std::queue <int > q;

    q.push(0);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        used[u]=0;

        for(int i=head[u];i;i=Next[i])

        {

            int v=to[i];

            if(!dep[v]&&edge[i]&&dis[v]>dis[u]+cost[i])

            {

                dis[v]=dis[u]+cost[i];

                pre[v]=i;

                if(!used[v]) {used[v]=1;q.push(v);}

            }

        }

    }

    return dis[t]!=inf;

}

void costflow()

{

    while(spfa())

    {

        int mi=inf;

        ans+=dis[t];

        for(int now=t;now;now=to[pre[now]^1])

            mi=mi>edge[pre[now]]?edge[pre[now]]:mi;

        for(int now=t;now;now=to[pre[now]^1])

            edge[pre[now]]-=mi,edge[pre[now]^1]+=mi;

    }

}

int main()

{

    init();

    costflow();

    printf("%.2lf",double(ans)/double(n));

    return 0;

}

---

2018.7.14