【NOI2012】美食节 | Mrsrz's blog

费用流，动态加点

题目大意：

有 $n$ 种菜 $m$ 个厨师。第 $j$ 个厨师做第 $i$ 种菜要花 $a_{i,j}$ 的时间。

现在点第 $i$ 种菜的有 $p_i$ 人。一个厨师同时只能做一道菜，多个厨师可以分别同时做菜。

问每个人需要等待的时间的总和最少是多少。

题解：

网络流。

厨师 $i$ 做第 $j$ 种菜，做的是他要做的倒数第 $k$ 道，那么有 $k$ 个人要等这道菜做完，产生的等待时间为 $a_{j,i}\times k$。

那我们把厨师拆成 $k$ 个点，每个点再分别向点每种菜的人连边，费用为 $k\times a_{j,i}$。

跑最小费用最大流即可。

由于 $a_{i,j}\geq0$，所以每次显然会先增广 $k$ 小的边（$0$ 的话没有影响不用管）。

但是这样边的个数会很多，过不去。

实际上，$\sum p_i$ 不是很大，增广的路径总数不多。也就是说有很多边是没用的。

再考虑刚刚那个东西，我们知道它会先增广 $k$ 小的边。

那我们每次增广一条路径，只有当前 $k$ 被增广的条件下，再新增 $k+1$ 这个点。

这样就大大减少了边数，可以通过。

Code：

#include<iostream>
#include<utility>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e4,T=9997,inf=0x3f3f3f3f;
struct edge{
    int to,nxt,cap,cost;
}e[2333333];
int n,m,p[N],head[N],cnt=1,nod;
int P[N],ck[888][888],a[888][888];
bool vis[N];
int dis[N],pre_e[N],aa[N];
long long ans;
pair<int,int>info[N];
inline void addedge(int u,int v,int cap,int cost){
    e[++cnt]=(edge){v,head[u],cap,cost},head[u]=cnt;
    e[++cnt]=(edge){u,head[v],0,-cost},head[v]=cnt;
}
void new_(int id,int k){
    ck[id][k]=++nod;
    addedge(0,nod,1,0);
    info[nod]=make_pair(id,k);
    for(int i=1;i<=n;++i)
    addedge(nod,P[i],1,k*a[id][i]);
}
queue<int>q;
bool MCMF(){
    memset(dis,0x3f,sizeof dis);
    memset(aa,0,sizeof aa);
    memset(pre_e,0,sizeof pre_e);
    aa[0]=inf;
    dis[0]=0;
    for(q.push(0);!q.empty();){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        if(e[i].cap&&dis[e[i].to]>dis[u]+e[i].cost){
            dis[e[i].to]=dis[u]+e[i].cost;
            aa[e[i].to]=min(e[i].cap,aa[u]);
            pre_e[e[i].to]=i;
            if(!vis[e[i].to])vis[e[i].to]=1,q.push(e[i].to);
        }
    }
    if(dis[T]>1e9)return 0;
    ans+=dis[T]*(long long)aa[T];
    for(int x=T;x;){
        int i=pre_e[x],pr=e[i^1].to;
        e[i].cap-=aa[T],e[i^1].cap+=aa[T];
        if(info[pr]!=make_pair(0,0)){
            int id=info[pr].first,k=info[pr].second;
            if(!ck[id][k+1])new_(id,k+1);
        }
        x=pr;
    }
    return 1;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>p[i];
        P[i]=++nod;
        addedge(P[i],T,p[i],0);
    }
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
    cin>>a[j][i];
    for(int i=1;i<=m;++i)
    new_(i,1);
    while(MCMF());
    cout<<ans<<'\n';
    return 0;
}