首页 > 代码库 > [BZOJ 1070][SCOI2007]修车(费用流)

[BZOJ 1070][SCOI2007]修车(费用流)

Description

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

Solution

非常经典的建图方式,将每一位技术人员拆成n个点分别他是表示倒数第几个修车的,倒数第k个修车的技术人员对所有在等待的人的贡献是tim[i][j]*k

#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<queue>#define INF 0x3f3f3f3f#define dot(x,y) (x+(y-1)*m)    //维修人员x在倒数第y的位置using namespace std;int s,t,n,m,head[1005],cnt=0,tim[70][10];int dis[5005],f[5005],pre[5005];bool inq[5005];int read(){    int x=0,f=1;char c=getchar();    while(c<0||c>9){if(c==-)f=-1;c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}    return x*f;}struct Node{    int next,from,to,cap,w;}Edges[500005];void addedge(int u,int v,int c,int w){    Edges[cnt].next=head[u];    head[u]=cnt;    Edges[cnt].from=u,Edges[cnt].to=v;    Edges[cnt].w=w;    Edges[cnt++].cap=c;}void insert(int u,int v,int c,int w){    addedge(u,v,c,w);    addedge(v,u,0,-w);}queue<int>q;int MCMF(){    int flow=0,cost=0;    while(1)    {        memset(dis,0x3f,sizeof(dis));        memset(f,0,sizeof(f));        q.push(s),pre[s]=-1,inq[s]=1,dis[s]=0,f[s]=INF;        while(!q.empty())        {            int u=q.front();            q.pop(),inq[u]=0;            for(int i=head[u];~i;i=Edges[i].next)            {                int v=Edges[i].to;                if(Edges[i].cap>0&&dis[v]>dis[u]+Edges[i].w)                {                    dis[v]=dis[u]+Edges[i].w;                    f[v]=min(f[u],Edges[i].cap);                    pre[v]=i;                    if(!inq[v])q.push(v),inq[v]=1;                }            }            }        if(dis[t]==INF)break;        flow+=f[t],cost+=dis[t]*f[t];        int p=t;        while(pre[p]!=-1)        {            Edges[pre[p]].cap-=f[t];            Edges[pre[p]^1].cap+=f[t];            p=Edges[pre[p]].from;        }    }    return cost;}int main(){    memset(head,-1,sizeof(head));    m=read(),n=read(),s=0,t=n*m*2+1;    for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)    {        insert(dot(j,i),t,1,0);        tim[i][j]=read();    //第i辆车被第j位维修员维修的时间 tim[i][j]        for(int k=1;k<=n;k++)        insert(n*m+i,dot(j,k),1,tim[i][j]*k);    }    for(int i=1;i<=n;i++)insert(s,n*m+i,1,0);    printf("%.2lf\n",(double)MCMF()/n);    return 0;}

 

[BZOJ 1070][SCOI2007]修车(费用流)