首页 > 代码库 > BZOJ 2879 美食节（费用流-动态加边）

BZOJ 2879 美食节（费用流-动态加边）

2024-07-09 00:11:16   225人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2879

题意：有n道菜，每道菜需要b[i]份，m个厨师，第j个厨师做第i道菜需要时间a[i][j]，求做完所有菜，所有人等待的最小总时间。

思路：设所有的菜为sum。一个明显的思路是将每个厨师拆成sum个点。然后sum个菜每个菜向每个厨师的每个点连边，表示该道菜为该厨师第几个做。由于这样数据太大。动态加边。每次增光一次后找到此次增广的厨师，每道菜将其连边。

 

struct node{    int u,v,next,cost,cap;};node edges[N*5];int head[N],e;void add(int u,int v,int cap,int cost){    e++;    edges[e].u=u;    edges[e].v=v;    edges[e].cap=cap;    edges[e].cost=cost;    edges[e].next=head[u];    head[u]=e;}void Add(int u,int v,int cap,int cost){    add(u,v,cap,cost);    add(v,u,0,-cost);}int pre[N],F[N],C[N],visit[N];int SPFA(int s,int t,int n){    int i;    for(i=0;i<=n;i++) F[i]=0,C[i]=INF,visit[i]=0;    queue<int> Q;    Q.push(s); F[s]=INF; C[s]=0;    int u,v,cost,cap;    while(!Q.empty())    {        u=Q.front();        Q.pop();                visit[u]=0;        for(i=head[u];i;i=edges[i].next)        {            if(edges[i].cap>0)            {                v=edges[i].v;                cost=edges[i].cost;                cap=edges[i].cap;                if(C[v]>C[u]+cost)                {                    C[v]=C[u]+cost;                    F[v]=min(F[u],cap);                    pre[v]=i;                    if(!visit[v]) visit[v]=1,Q.push(v);                }            }        }    }    return F[t];}int s,t,n,m,a[55][105],b[105],cnt[105],last[105];int main(){    RD(n,m);    int sum=0,i,j,x;    FOR1(i,n) RD(b[i]),sum+=b[i];    e=1;    s=0; t=n+m+sum+1;    FOR1(i,n)     {        Add(s,i,b[i],0);        FOR1(j,m)         {            RD(a[i][j]);            Add(i,n+j,1,a[i][j]);        }    }    FOR1(i,m)    {        cnt[i]=1;        Add(n+i,t,1,0);        last[i]=e;    }    int ans=0,temp;    while(sum--)    {        temp=SPFA(s,t,t);        for(i=t;i!=s;i=edges[pre[i]].u)        {            x=pre[i];            ans+=temp*edges[x].cost;            edges[x].cap-=temp;            edges[x^1].cap+=temp;        }        for(j=1;j<=m&&edges[last[j]-1].cap;j++);        cnt[j]++;        FOR1(i,n) Add(i,n+m+sum,1,a[i][j]*cnt[j]);        Add(n+m+sum,t,1,0);        last[j]=e;    }    PR(ans);}

 

 

 


联系
我们