题解 P2050 【[NOI2012]美食节】

Froggy · 2020-02-19 23:06:15 · 题解

这是一道非常好的动态加点的费用流题目。

是这道题目： P2053 [SCOI2007]修车的加强版。

建模：

我们先按那道题的思路：把“厨师”分层。

如果第 j 个厨师先后做了第 a_1,a_2,\cdots,a_w 种菜，那么等待时间之和就是：

t_{a_1,j}w+t_{a_2,j}(w-1)+\cdots+t_{a_w,j}

第 k 项的意思是做了第 k 道菜让后面的 w-k 道菜每个都等了 t_{a_k,j} 的时间。

那么我们让第 j 个厨师的第 w 层表示第 j 个厨师做了倒数 w 道菜。方便起见，把它用 (j,w) 表示。(w\in [1,p])

它与第 i 道菜连边就表示第 j 个厨师做的倒数第 t 道菜是第 i 种菜。

设源点为 S ，汇点为 T ，菜的编号为 1\sim n，”分层厨师“ 就用上面说的 (j,w) 表示。

从源点向每道菜连一条流量为 p_i，费用为 0 的边，表示第 i 中菜需要做 p_i 道。
每个 (j,w) 向汇点连一条流量为 1，费用为 0 的边，表示第 j 个厨师做倒数第 w 道菜。
每道菜向每个 (j,w) 连一条边权为 1，费用为 t_{i,j}\times w 的边，表示第 i 种菜的其中一道是第 j 个厨师做的倒数第 w 道菜，根据开头给出的那个式子可知，它贡献的费用是 t_{i,j}\times w。

这样连为什么正确呢？

根据贪心的思想，设第 j 个厨师做了 w_j 道菜，那么被用到的点一定是 (j,1)\sim (j,w_j) 连续的。

假设是断续的，由于中间没有被用到的层需要的费用一定比后面的层所需要的费用小，所以断续的情况一定不是最优的。

这样做点数的规模是 \mathcal{O}(mp+n) 的，边数的规模是 \mathcal{O}(nmp) 的。

根据这个建图，就能获得 60pts 的好成绩！-> code

优化建图：

其实根据上面的建模可以发现，好多 (j,w) 的点是没有用到的。

根据上述的贪心证明可知：被用到的一定是从 (j,1) 开始的连续的几个层。

那么我们为什么不一边跑流一边加点呢？这样我们就能省去很多无用的点。

我们设第 j 个厨师已经加到了第 top_j 层。若再一次跑流之后，(j,top_j) 被用掉了，那么我们直接把 (j,top_j+1) 加进图里面就好了。

这样点数的规模就降到了 \mathcal{O}(n+m+p)，边数的规模降到了 \mathcal{O}(np)。

现在的重点就是怎么判断 (j,top_j) 是否被跑过了：

我看大部分人写的都是KM，每次只增广一条路，这样很容易判断被用掉的”分层厨师“ 的位置。

其实，多路增广的Dinic也很好判断。有两种方法：

1.直接看与汇点 T 相连的边的流是否被跑满。

2.直接看 (j,top_j) 是否被某一条增广路经过。

第2种实现起来更简单，并且常数小，直接在跑流的时候打标记就好了。

注意： 不能类似二分图一样用经过 (j,top_j) 的流的走向去判断，因为可能存在增广路满足经过 (j,top_j) 但下一个节点不是 T。所以无论这条增广路的走向如何，只要经过了 (j,top_j) 那么 (j,top_j) 一定被用过。

~~这样说的话是不是方法1更好理解呢qwq~~

Dinic跑费用流超快的呢！开O2时候还不到 1.3s！评测记录

(我很奇怪为什么现在大部分人跑费用流喜欢用KM）

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf=0x3f3f3f3f;
#define N 103234
inline 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<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
int m,n,cnt,vis[N],dis[N],c[55][105],p[N],sum,top[N],nxt[N];
int head[N],mincost,S,T;
queue<int> q;
struct Edge{
    int to,nxt,val,cost;
}edge[N<<5];
inline void add(int a,int b,int c,int d){
    ++cnt;
    edge[cnt].to=b;
    edge[cnt].val=c;
    edge[cnt].cost=d;
    edge[cnt].nxt=head[a];
    head[a]=cnt;
}
bool SPFA(){
    memset(dis,0x3f,sizeof(dis));
    q.push(S);
    dis[S]=0;
    vis[S]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(edge[i].val&&dis[v]>dis[u]+edge[i].cost){
                dis[v]=dis[u]+edge[i].cost;
                if(!vis[v]){
                    q.push(v),vis[v]=1;
                }
            }
        }
    }
    return dis[T]<inf;
}
int dfs(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    vis[u]=1;
    for(int i=head[u];i&&limit;i=edge[i].nxt){
        int v=edge[i].to;
        if(edge[i].val&&!vis[v]&&dis[v]==dis[u]+edge[i].cost){
            int k=dfs(v,min(limit,edge[i].val));
            if(k>0){
                edge[i].val-=k;
                edge[i^1].val+=k;
                limit-=k;
                flow+=k;
                mincost+=k*edge[i].cost;
                nxt[u]=v;
            }
        }
    }
    if(!flow)dis[u]=inf;
    vis[u]=0;
    return flow;
}
inline int ID(int x,int y){
    return (x-1)*sum+y;
}
int Dinic(){
    int maxflow=0;
    while(SPFA()){
        maxflow+=dfs(S,inf);
        for(int j=1;j<=m;j++){
            if(nxt[n+ID(j,top[j])]&&top[j]<sum){//判断是否被一条增广路经过
                ++top[j];
                int now=n+ID(j,top[j]);
                for(int i=1;i<=n;i++){
                    add(i,now,1,c[i][j]*top[j]);
                    add(now,i,0,-c[i][j]*top[j]);
                }
                add(now,T,1,0);
                add(T,now,0,0);
            }
        } 
    }
    return maxflow;
}
int main(){
    n=read(),m=read(),cnt=1;
    for(int i=1;i<=n;i++){
        p[i]=read();sum+=p[i];
    }
    S=m*sum+n+1,T=m*sum+n+2;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            c[i][j]=read();
        }
    }
    for(int i=1;i<=n;i++){
        add(S,i,p[i],0),add(i,S,0,0);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            add(i,n+ID(j,1),1,c[i][j]);
            add(n+ID(j,1),i,0,-c[i][j]);
        }
    }
    for(int i=1;i<=m;i++){
        top[i]=1;
        add(n+ID(i,1),T,1,0);
        add(T,n+ID(i,1),0,0);
    }
    Dinic();
    printf("%d\n",mincost);
    return 0;
}

Froggy's blog

题解 P2050 【[NOI2012]美食节】

建模：

优化建图：

呱!!