BZOJ 1070: [SCOI2007]修车 [最小费用最大流]

2023-08-20 08:03:40

1070: [SCOI2007]修车

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 4936 Solved: 2032
[Submit][Status][Discuss]

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)

理解错了题意：每个人可以修多辆车

每个人拆成n个点，对于他修的倒数第一辆代价就是1*time，倒数第二辆就是2*time，一次类推

每个点都像车连一条容量为1，代价为以上时间的边

s连所有人，t连所有车，跑费用流即可

注意先m后n

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long ll;

const int N=,M=1e5+,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,m,a[N][N],s,t;

struct edge{

    int v,ne,c,f,w;

}e[M<<];

int cnt,h[N];

inline void ins(int u,int v,int c,int w){

    cnt++;

    e[cnt].v=v;e[cnt].c=c;e[cnt].f=;e[cnt].w=w;

    e[cnt].ne=h[u];h[u]=cnt;

    cnt++;

    e[cnt].v=u;e[cnt].c=;e[cnt].f=;e[cnt].w=-w;

    e[cnt].ne=h[v];h[v]=cnt;

}

inline int id(int i,int j){return (i-)*n+j;}

void build(){

    s=;t=m*n+n+;int num=m*n;

    for(int i=;i<=m;i++)

        for(int j=;j<=n;j++){

            int t=id(i,j);

            ins(s,t,,);

            for(int k=;k<=n;k++) ins(t,num+k,,a[i][k]*j);

        }

    for(int i=;i<=n;i++) ins(num+i,t,,);

}

int q[N],head,tail,d[N],inq[N],pre[N],pos[N];

inline void lop(int &x){if(x==N) x=;else if(x==) x=N-;}

bool spfa(){

    memset(d,,sizeof(d));

    memset(inq,,sizeof(inq));

    head=tail=;

    q[tail++]=s;inq[s]=;d[s]=;

    pre[t]=-;

    while(head!=tail){

        int u=q[head++];inq[u]=;lop(head);

        for(int i=h[u];i;i=e[i].ne){

            int v=e[i].v,w=e[i].w;

            if(e[i].c>e[i].f&&d[v]>d[u]+w){

                d[v]=d[u]+w;

                pos[v]=i;pre[v]=u;

                if(!inq[v]){

                    inq[v]=;

                    if(d[v]<d[q[head]]) head--,lop(head),q[head]=v;

                    else q[tail++]=v,lop(tail);

                }

            }

        }

    }

    return pre[t]!=-;

}

int mcmf(){

    int flow=,cost=;

    while(spfa()){

        int f=INF;

        for(int i=t;i!=s;i=pre[i]) f=min(f,e[pos[i]].c-e[pos[i]].f);

        flow+=f;cost+=d[t]*f;

        for(int i=t;i!=s;i=pre[i]){

            int p=pos[i];

            e[p].f+=f;

            e[((p-)^)+].f-=f;

        }

    }

    return cost;

}

int main(){

    m=read();n=read();

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

        for(int j=;j<=m;j++) a[j][i]=read();//

    build();

    printf("%.2f",(double)mcmf()/n);

}

码农公寓