• 题面描述
    • \(CZ\)市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。作为一个喜欢尝鲜的美食客，小\(M\)自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小\(M\)仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小\(M\)开始研究起了做菜顺序的问题，即安排一个做菜的顺序使得同学们的等待时间最短。小\(M\)发现，美食节共有\(n\)种不同的菜品。每次点餐，每个同学可以选择其中的一个菜品。总共有\(m\)个厨师来制作这些菜品。当所有的同学点餐结束后，菜品的制作任务就会分配给每个厨师。然后每个厨师就会同时开始做菜。厨师们会按照要求的顺序进行制作，并且每次只能制作一人份。此外，小\(M\)还发现了另一件有意思的事情: 虽然这\(m\)个厨师都会制作全部的\(n\)种菜品，但对于同一菜品，不同厨师的制作时间未必相同。他将菜品用\(1, 2, ..., n\)依次编号，厨师用\(1, 2, ..., m\)依次编号，将第\(j\)个厨师制作第\(i\)种菜品的时间记为 \(t_{i,j}\) 。小\(M\)认为：每个同学的等待时间为所有厨师开始做菜起，到自己那份菜品完成为止的时间总长度。换句话说，如果一个同学点的菜是某个厨师做的第\(k\)道菜，则他的等待时间就是这个厨师制作前\(k\)道菜的时间之和。而总等待时间为所有同学的等待时间之和。现在，小\(M\)找到了所有同学的点菜信息: 有 \(p_i\) 个同学点了第i种菜品\((i=1, 2, ..., n)\)。他想知道的是最小的总等待时间是多少。
  • 输入格式
    • 输入文件的第\(1\)行包含两个正整数\(n\)和\(m\)，表示菜品的种数和厨师的数量。 第\(2\)行包含\(n\)个正整数，其中第\(i\)个数为\(p_i\)，表示点第\(i\)种菜品的人数。 接下来有\(n\)行，每行包含\(m\)个非负整数，这\(n\)行中的第\(i\)行的第\(j\)个数为\(t_{i,j}\)，表示第\(j\)个厨师制作第\(i\)种菜品所需的时间。 输入文件中每行相邻的两个数之间均由一个空格隔开，行末均没有多余空格。
  • 输出格式
    • 输出仅一行包含一个整数，为总等待时间的最小值。
  • 题解
    • bzoj1070 修车 的数据加强版，按之前\(dinic\)复杂度\(O(n^3m^2\sqrt{m})\)肯定过不去
    • 考虑在增广倒数第\(i\)道菜的边前，不可能先增广倒数第\(i+1\)道菜的边
    • 因此可以动态加边，当一个厨师的倒数第\(i\)道菜被增广后再加第\(i+1\)道菜的边，\(dinic\)总复杂度\(O((n+m)^2\sqrt{nm})\)
  • 备注
    • 动态加边费用流不能用\(dij-势能法\)加速增广路寻找
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=1e5+5;
const int MAXM=3e6+6;
const int inf=1e9;
int edge=1,head[MAXN],tail[MAXM],nex[MAXM],w[MAXM],r[MAXM];
int d[MAXN],h[MAXN],preu[MAXN],pree[MAXN];
bool use[MAXN];
int n,m,S,T,tot;
int p[45],a[45][105],pos[105];
struct rq{
    int u,d;
    bool operator < (const rq& b) const {
        return d>b.d;
    }
};
//priority_queue<rq> q;
queue<int> q;
void add(int u,int v,int R,int W){
    edge++,nex[edge]=head[u],head[u]=edge,tail[edge]=v,w[edge]=W,r[edge]=R;
}
void ins(int u,int v,int R,int W){
    add(u,v,R,W); add(v,u,0,-W);
}
/*bool dij(){
    for (int i=1;i<=T;i++) d[i]=inf,use[i]=0;
    for (int i=1;i<=T;i++) preu[i]=pree[i]=0;
    d[S]=0; q.push((rq){S,0});
    while (!q.empty()){
        rq u=q.top(); q.pop();
//      cout<<u.u<<endl;
        if (use[u.u]) continue;
        use[u.u]=1;
        for (int e=head[u.u];e;e=nex[e]){
            int v=tail[e];
            int W=h[u.u]+w[e]-h[v];
            if (d[v]>d[u.u]+W&&r[e]>0){
                d[v]=d[u.u]+W;
                preu[v]=u.u; pree[v]=e;
                q.push((rq){v,d[v]});
            }
        }
    }
    cout<<"T: "<<d[T]<<endl;
    return d[T]<inf;
}*/
bool xpfa(){
    for (int i=1;i<=T;i++) d[i]=inf,use[i]=0;
    d[S]=0; q.push(S); use[S]=1;
    while (!q.empty()){
        int u=q.front(); q.pop();
        use[u]=0;
        for (int e=head[u];e;e=nex[e]){
            int v=tail[e];
            if (d[v]>d[u]+w[e]&&r[e]>0){
                d[v]=d[u]+w[e];
                preu[v]=u; pree[v]=e;
                if (!use[v]) q.push(v),use[v]=1;
            }
        }
    }
    return d[T]<inf;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&p[i]),tot+=p[i];
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) scanf("%d",&a[i][j]);
    }
    S=n+m*tot+1; T=S+1;
    for (int i=1;i<=n;i++) ins(S,i,p[i],0);
    for (int i=n+1;i<=n+m*tot;i++) ins(i,T,1,0);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            ins(i,n+(j-1)*tot+tot,1,a[i][j]);
            pos[j]=tot;
        }
    }
    int cost=0,flow=0;
    while (xpfa()){
        int res=inf;
        for (int u=T;u!=S;u=preu[u]){
            int v=preu[u],e=pree[u];
            res=min(res,r[e]);
        }
        flow+=res; cost+=res*d[T];
        for (int u=T;u!=S;u=preu[u]){
            int v=preu[u],e=pree[u];
            r[e]-=res; r[e^1]+=res;
        }
        int tmp1=preu[T];
        tmp1=(tmp1-1-n)/tot+1;
        int tmp3=pos[tmp1];
//      cout<<tmp1<<" "<<tmp3<<" "<<res<<" "<<cost<<endl;
        if (tmp3==1) continue;
//      cout<<"add: ";
        for (int i=1;i<=n;i++){
            ins(i,n+(tmp1-1)*tot+tmp3-1,1,a[i][tmp1]*(tot-(tmp3-1)+1));
//          cout<<n+(tmp1-1)*tot+tmp3-1<<" ";
        }
//      cout<<endl;
        pos[tmp1]--;
    }
    printf("%d\n",cost);
    return 0;
}
  • 附一个错误的dij版
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=1e5+5;
const int MAXM=3e6+6;
const int inf=1e9;
int edge=1,head[MAXN],tail[MAXM],nex[MAXM],w[MAXM],r[MAXM];
int d[MAXN],h[MAXN],preu[MAXN],pree[MAXN];
bool use[MAXN];
int n,m,S,T,tot;
int p[45],a[45][105],pos[105];
struct rq{
    int u,d;
    bool operator < (const rq& b) const {
        return d>b.d;
    }
};
priority_queue<rq> q;
//queue<int> q;
void add(int u,int v,int R,int W){
    edge++,nex[edge]=head[u],head[u]=edge,tail[edge]=v,w[edge]=W,r[edge]=R;
}
void ins(int u,int v,int R,int W){
    add(u,v,R,W); add(v,u,0,-W);
}
bool dij(){
    for (int i=1;i<=T;i++) d[i]=inf,use[i]=0;
    for (int i=1;i<=T;i++) preu[i]=pree[i]=0;
    d[S]=0; q.push((rq){S,0});
    while (!q.empty()){
        rq u=q.top(); q.pop();
//      cout<<u.u<<endl;
        if (use[u.u]) continue;
        use[u.u]=1;
        for (int e=head[u.u];e;e=nex[e]){
            int v=tail[e];
            int W=h[u.u]+w[e]-h[v];
            if (d[v]>d[u.u]+W&&r[e]>0){
                d[v]=d[u.u]+W;
                preu[v]=u.u; pree[v]=e;
                q.push((rq){v,d[v]});
            }
        }
    }
//  cout<<"T: "<<d[T]<<endl;
    return d[T]<inf;
}
/*bool xpfa(){
    for (int i=1;i<=T;i++) d[i]=inf,use[i]=0;
    d[S]=0; q.push(S); use[S]=1;
    while (!q.empty()){
        int u=q.front(); q.pop();
        use[u]=0;
        for (int e=head[u];e;e=nex[e]){
            int v=tail[e];
            if (d[v]>d[u]+w[e]&&r[e]>0){
                d[v]=d[u]+w[e];
                preu[v]=u; pree[v]=e;
                if (!use[v]) q.push(v),use[v]=1;
            }
        }
    }
    return d[T]<inf;
}*/
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&p[i]),tot+=p[i];
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) scanf("%d",&a[i][j]);
    }
    S=n+m*tot+1; T=S+1;
    for (int i=1;i<=n;i++) ins(S,i,p[i],0);
    for (int i=n+1;i<=n+m*tot;i++) ins(i,T,1,0);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            ins(i,n+(j-1)*tot+tot,1,a[i][j]);
            pos[j]=tot;
        }
    }
    int cost=0,flow=0;
//  while (xpfa()){
    while (dij()){
        for (int i=1;i<=T;i++) h[i]+=d[i];
        int res=inf;
        for (int u=T;u!=S;u=preu[u]){
            int v=preu[u],e=pree[u];
            res=min(res,r[e]);
        }
        flow+=res; cost+=res*h[T];
        for (int u=T;u!=S;u=preu[u]){
            int v=preu[u],e=pree[u];
            r[e]-=res; r[e^1]+=res;
        }
        int tmp1=preu[T];
        tmp1=(tmp1-1-n)/tot+1;
        int tmp3=pos[tmp1];
//      cout<<tmp1<<" "<<tmp3<<" "<<res<<" "<<cost<<endl;
        if (tmp3==1) continue;
//      cout<<"add: ";
        for (int i=1;i<=n;i++){
            ins(i,n+(tmp1-1)*tot+tmp3-1,1,a[i][tmp1]*(tot-(tmp3-1)+1));
//          cout<<n+(tmp1-1)*tot+tmp3-1<<" ";
        }
//      cout<<endl;
        pos[tmp1]--;
    }
    printf("%d\n",cost);
    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄