P2050 [NOI2012]美食节

题意

这题是P2053 [SCOI2007]修车的增强版。

我们直接跳过建图，说优化，建图见我的这篇博客。

我们发现边数+点数很大，将所有边和点都建出来肯定会超时，因此我们用网络流动态开点的思想解决。

先只建做倒数第一道菜的点，之后我们跑最大流，记下所有满流的厨师点，对于这些点我们再建出下一阶段的点。

code:

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
const int maxn=50;
const int maxm=110;
const int inf=1e9;
int n,m,cnt=1,S,T,sum,tot;
int val[maxn],head[5010],dis[5010];
int t[maxn][maxm];
bool vis[5010],check[5010],used[5010];
pii pos[5010];
struct edge{int to,nxt,flow,cost;}e[5000010];
inline int read()
{
    char c=getchar();int res=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
    return res*f;
}
inline void add(int u,int v,int w,int c)
{
    e[++cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].to=v;
    e[cnt].flow=w;
    e[cnt].cost=c;
}
inline void addflow(int u,int v,int w,int c){add(u,v,w,c);add(v,u,0,-c);}
inline bool spfa()
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(S);dis[S]=0;vis[S]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();vis[x]=0;
        //cout<<x<<' '<<pos[x].fir<<' '<<pos[x].sec<<endl;
        for(int i=head[x];i;i=e[i].nxt)
        {
            if(e[i].flow<=0)continue;
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].cost)
            {
                dis[y]=dis[x]+e[i].cost;
                if(!vis[y])q.push(y),vis[y]=1;
            }
        }
    }
    return dis[T]!=0x3f3f3f3f;
}
int dfs(int x,int lim)
{
    if(x==T||lim<=0)return lim;
    vis[x]=1;
    int res=lim;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(e[i].flow<=0||vis[y]||dis[y]!=dis[x]+e[i].cost)continue;
        int tmp=dfs(y,min(res,e[i].flow));
        if(tmp>0)check[x]=check[y]=1;
        res-=tmp;
        e[i].flow-=tmp,e[i^1].flow+=tmp;
        if(res<=0)break;
    }
    return lim-res;
}
inline int Dinic()
{
    int flow=0,cost=0;
    while(flow<sum)
    {
        while(spfa())
        {
            memset(check,0,sizeof(check));
            int tmp=dfs(S,inf);
            flow+=tmp;cost+=tmp*dis[T];
            int nowtot=tot;
            for(int i=1;i<=nowtot;i++)
                if(pos[i].fir&&check[i]&&!used[i])
                {
                    used[i]=1;
                    pos[++tot]=mkp(pos[i].fir,pos[i].sec+1);
                    for(int j=1;j<=n;j++)addflow(j,tot,1,pos[tot].sec*t[j][pos[tot].fir]);
                    addflow(tot,T,1,0);
                }
        }
    }
    return cost;
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++)val[i]=read(),sum+=val[i];
    S=0,T=5000;
    for(int i=1;i<=n;i++)addflow(S,i,val[i],0);
    tot=n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            t[i][j]=read();
    for(int i=1;i<=m;i++)pos[++tot]=mkp(i,1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            addflow(i,n+j,1,t[i][j]);
    for(int i=n+1;i<=tot;i++)addflow(i,T,1,0);
    printf("%d",Dinic());
    return 0;
}

P2050 [NOI2012]美食节

原文：https://www.cnblogs.com/nofind/p/12098270.html