题解P2050【美食节】　费用流

# 题目分析 ## 建图模型 这题就是P2053修车的数据加强版，那么建图方式也差不多。 对于每个菜建立一个点，源点向其连一条流量为需求量费用为０的边。 然后再建一层点，分别表示第j个厨师做第倒数i道菜。向汇点连一条流量为１费用为０的边。 假设有一个点表示第j个厨师做第倒数k道菜，那么对于菜i，向其连一条流量为１，费用为k×a(i,j)的边。这表示第j个厨师做的倒数第k道菜是菜i，那么就要做a(i,j)这么长的时间，有k个人要等这么长的时间。 意会一下可以发现，这个模型能解决“同时做”问题。 ## 优化 由于此题数据量很大，把所有边连完后再跑费用流是一定会GG的（60分） 由于我们跑一次spfa只能找出一次增广路，所以我们可以暂时不连不需要的边。一开始，我们把所有厨师做倒数第１道菜与所有菜连好，然后找一条增广路，这条增广路上一定经过了一个点，表示第j个厨师做倒数第１道菜，于是我们添加点（第j个厨师做倒数第２道菜），与汇点和所有菜连边，以此类推。 意会一下可以发现，这样每次spfa的时候，需要的边都被连上了。 # 代码 ```cpp #include<bits/stdc++.h> using namespace std; const int N=100005,M=1e7+5,inf=0x3f3f3f3f;//边一定要开大 int m,n,tot=1,sum,S,T,ans; int p[44],a[44][105],dish[N],cook[N]; int h[N],ne[M],to[M],flow[M],w[M],dis[N],liu[N],pre[N],inq[N]; void add(int x,int y,int z,int c) { to[++tot]=y,ne[tot]=h[x],h[x]=tot,flow[tot]=z,w[tot]=c; to[++tot]=x,ne[tot]=h[y],h[y]=tot,flow[tot]=0,w[tot]=-c; } int bfs() {//费用流：主干部分 for(int i=S;i<=T;++i) dis[i]=inf,inq[i]=pre[i]=0; queue<int>q;int x; liu[S]=inf,dis[S]=0,q.push(S); while(!q.empty()) { x=q.front(),q.pop(),inq[x]=0; for(int i=h[x];i;i=ne[i]) if(flow[i]>0&&dis[x]+w[i]<dis[to[i]]) { dis[to[i]]=dis[x]+w[i],pre[to[i]]=i; liu[to[i]]=min(liu[x],flow[i]); if(!inq[to[i]]) inq[to[i]]=1,q.push(to[i]); } } if(!pre[T]) return 0; x=T; while(x!=S) { int kl=pre[x]; flow[kl]-=liu[T],flow[kl^1]+=liu[T]; ans+=w[kl]*liu[T],x=to[kl^1]; } return 1; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d",&p[i]),sum+=p[i]; for(int i=1;i<=n;++i) add(0,i+sum*m,p[i],0); S=0,T=sum*m+n+1; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&a[i][j]),add(i+sum*m,(j-1)*sum+1,1,a[i][j]);//预先加上所有菜被厨师倒数第１个做 for(int i=1;i<=m;++i) add((i-1)*sum+1,T,1,0);//预先加上所有厨师做倒数第１道菜 for(int i=1;i<=m;++i) for(int j=1;j<=sum;++j) { int tmp=(i-1)*sum+j; dish[tmp]=j,cook[tmp]=i; //这是本蒟蒻为了方便解码而写的，表示tmp这个点代表cool[tmp]做倒数第dish[tmp]道菜 } while(bfs()) { int tmp=to[pre[T]^1]; add(tmp+1,T,1,0);//添加新的边，说明见上 for(int i=1;i<=n;++i) add(i+m*sum,tmp+1,1,a[i][cook[tmp]]*(dish[tmp]+1)); } printf("%d",ans); return 0; } ```