[NOI2012] 美食节 - 费用流

和SCOI2007 修车 差不多，但带着修车的思维定势来做可能会gg……
______________
有\(N\)种菜品，每种要求\(P_i\)个。有\(M\)个厨师，每个厨师做每个菜的时间可能不同。要求最小化顾客的总等待时间。
___________________
考虑运用“时间拆点”大法，将每个厨师拆成\(P\)个。（注意这里是\(P\)不是\(N\)）
每个菜可以任意选择将它的一份分配给某个厨师做，于是将每种菜对应的点向所有的“厨师时间”连边，费用即为厨师在他的该时间（顺序）做这个菜所用的时间对于答案的贡献。
然后就将\(S\)向每种菜连边，权值按\(P_i\)；每个“厨师时间”向\(T\)连边，权值为1。费用流得到答案。
______________________

• 极端情况下可能有一个厨师处理\(P\)道菜的情况发生
• 本题中不会出现重边
• 记得给SPFA加上SLF和LLL优化（以下代码没加）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#define G g
using namespace std;
struct Item{int p,v,c;};
Item item(int _p,int _v,int _c){Item it;it.p=_p;it.v=_v;it.c=_c;return it;}
vector <Item> g[200005];
int n,m,t1,t2,t3,dis[200005],d[200005],vis[200005],s,t,t4,costs=0,tans,ans,inc[200005],cnt=0,S,ax[1005][1005],bx[1005],edg[200005],realist[1005][1005],reali[200005],realj[200005];
deque <int> q;
vector <int> oppo[200005];
void realcreate(int i,int j);
int dinic_spfa(){
    memset(dis,0xff,sizeof dis);
    memset(d,0x3f,sizeof d);
    memset(vis,0x00,sizeof vis);
    memset(inc,0x00,sizeof inc);
    q.push_back(s); dis[s]=0; d[s]=0;
    while(!q.empty()){ 
        int p=q.front(); q.pop_front(); vis[p]=0; inc[p]++;
        for(int i=0;i<g[p].size();i++)
            if(d[g[p][i].p]>d[p]+g[p][i].v&&g[p][i].c>0){
                dis[g[p][i].p]=p;
                d[g[p][i].p]=d[p]+g[p][i].v;
                if(vis[g[p][i].p]==0) {
                    vis[g[p][i].p]=1;
                    if(q.push(g[p][i].p);
                }}}
    return dis[t]>0;}
int dinic_dfs(){
    int p=t,a=0x7fffffff;
    while(p-s){
        for(int i=0;i<G[dis[p]].size();i++)
            if(G[dis[p]][i].p==p){
                a=min(G[dis[p]][i].c,a);
                p=dis[p];break;}}   
    p=t;
    while(p-s){
        if(p>0&&p<100000) realcreate(reali[p]+1,realj[p]);
        for(int i=0;i<G[p].size();i++)
            if(G[p][i].p==dis[p])
                G[p][i].c+=a;
        for(int i=0;i<G[dis[p]].size();i++)
            if(G[dis[p]][i].p==p)
                G[dis[p]][i].c-=a,
                costs+=a*G[dis[p]][i].v;
        p=dis[p];}
    return a;}
int dinic_main(int src,int dest){
    s=src; t=dest; 
    while(dinic_spfa()) ans+=dinic_dfs();
    return ans;}
void build(int w,int x,int y,int z){
    g[w].push_back(item(x,z,y));
    g[x].push_back(item(w,-z,0));} 
void realcreate(int i,int j){ 
    if(realist[i][j]) return;
    realist[i][j]=1;
    ++cnt; reali[cnt]=i; realj[cnt]=j;
    //printf("real %d %d\n",i,j);
    build(cnt,100000+n+1,1,0);
    for(int k=1;k<=n;k++) // 菜品编号k 
        build(100000+k,cnt,1,i*ax[k][j]);}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&bx[i]);
    for(int i=1;i<=n;i++) build(0,100000+i,bx[i],0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&ax[i][j]);
    for(int i=1;i<=1;i++) // 位于该厨师的倒数第i个菜品 
        for(int j=1;j<=m;j++) // 厨师编号m 
            realcreate(i,j);
    dinic_main(0,100000+n+1);
    printf("%d\n",costs);
}

[NOI2012] 美食节 - 费用流

原文：https://www.cnblogs.com/mollnn/p/12324398.html