洛谷P2050 [NOI2012]美食节

题目大意：

懒得大意了，自己看吧

一开始的想法是做一个类似串联的关系（？），如果让某个厨师做第\(k\)道菜那么前\(k-1\)道菜的代价都要算上

然后发现不太行

那就反着定义，定义\(id[i][j]\)是第\(i\)个厨师做的第\(j\)道菜，那么第\(k\)个菜品向这个节点连边的边权就是\(val[i][k]*j\)

不过点数达到了\(O(mp)\)有点跑不过

考虑不可能每个厨师都做\(p\)道菜，而且我们的费用流每次只找一条增广路

那么我们先建出每个厨师的最后一道菜，然后让费用流去找增广路，其中必定经过一个\(id[i][j]\)，我们再建出这个厨师的下一个节点

费用流部分复杂度不会退化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
namespace red{
#define eps (1e-8)
    inline int read()
    {
        int x=0;char ch,f=1;
        for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
        if(ch=='-') f=0,ch=getchar();
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
        return f?x:-x;
    }
    const int N=1e5+10;
    int n,m,st,ed,tot;
    int cook[N],tim[110][50],sum;
    int id[110][810];//第i个厨师做的倒数第j个菜
    int head[N],cnt=1;
    struct point
    {
        int nxt,to,c,val;
        point(){}
        point(const int &nxt,const int &to,const int &c,const int &val):nxt(nxt),to(to),c(c),val(val){}
    }a[N<<7];
    inline void link(int x,int y,int c,int val)
    {
        a[++cnt]=(point){head[x],y,c,val};head[x]=cnt;
        a[++cnt]=(point){head[y],x,0,-val};head[y]=cnt;
    }
    struct node
    {
        int x,y;//第x个厨师做到倒数第y道菜
    }eva[N];
    int pre[N],dis[N],f[N],eg[N];
    bool vis[N];
    queue<int> q;
    inline bool spfa()
    {
        memset(vis,0,sizeof(vis));vis[st]=1;
        memset(dis,0x3f,sizeof(dis));dis[st]=0;
        memset(f,0x3f,sizeof(f));
        q.push(st);pre[ed]=0;
        while(!q.empty())
        {
            int now=q.front();
            q.pop();
            vis[now]=0;
            for(int i=head[now];i;i=a[i].nxt)
            {
                int t=a[i].to;
                if(dis[t]>dis[now]+a[i].val&&a[i].c)
                {
                    dis[t]=dis[now]+a[i].val;
                    eg[t]=i;
                    pre[t]=now;
                    f[t]=min(f[now],a[i].c);
                    if(!vis[t])
                    {
                        vis[t]=1;
                        q.push(t);
                    }
                }
            }
        }
        return pre[ed];
    }
    inline int dinic()
    {
        int ret=0;
        while(spfa())
        {
            int now=ed;
            ret+=f[now]*dis[now];
            int tmp=pre[now];
            id[eva[tmp].x][eva[tmp].y+1]=++tot;
            eva[tot].x=eva[tmp].x,eva[tot].y=eva[tmp].y+1;
            for(int i=1;i<=n;++i) link(cook[i],tot,1,tim[eva[tot].x][i]*eva[tot].y);
            link(tot,ed,1,0);
            while(now!=st)
            {
                a[eg[now]].c-=f[ed];
                a[eg[now]^1].c+=f[ed];
                now=pre[now];
            }
        }
        return ret;
    }
    inline void main()
    { 
        n=read(),m=read();
        //每个厨师拆成p个点，每道菜拆成2个点
        st=++tot,ed=++tot;
        for(int tmp,i=1;i<=n;++i)
        {
            tmp=read();
            sum+=tmp;
            cook[i]=++tot;
            link(st,cook[i],tmp,0);
        }
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=m;++j)
            {
                tim[j][i]=read();
            }
        }
        for(int i=1;i<=m;++i)
        {
            id[i][1]=++tot;
            eva[tot].x=i,eva[tot].y=1;
            for(int k=1;k<=n;++k)
            {
                link(cook[k],tot,1,tim[i][k]);
            }
            link(tot,ed,1,0);
        }
        printf("%d\n",dinic());
    }
}
signed main()
{
    red::main();
return 0;
}

洛谷P2050 [NOI2012]美食节

原文：https://www.cnblogs.com/knife-rose/p/12110847.html