题解P2050【美食节】 费用流
题目分析
建图模型
这题就是P2053修车的数据加强版，那么建图方式也差不多。
对于每个菜建立一个点，源点向其连一条流量为需求量费用为０的边。
然后再建一层点，分别表示第j个厨师做第倒数i道菜。向汇点连一条流量为１费用为０的边。
假设有一个点表示第j个厨师做第倒数k道菜，那么对于菜i，向其连一条流量为１，费用为k×a(i,j)的边。这表示第j个厨师做的倒数第k道菜是菜i，那么就要做a(i,j)这么长的时间，有k个人要等这么长的时间。
意会一下可以发现，这个模型能解决“同时做”问题。
优化
由于此题数据量很大，把所有边连完后再跑费用流是一定会GG的（60分）
由于我们跑一次spfa只能找出一次增广路，所以我们可以暂时不连不需要的边。一开始，我们把所有厨师做倒数第１道菜与所有菜连好，然后找一条增广路，这条增广路上一定经过了一个点，表示第j个厨师做倒数第１道菜，于是我们添加点（第j个厨师做倒数第２道菜），与汇点和所有菜连边，以此类推。
意会一下可以发现，这样每次spfa的时候，需要的边都被连上了。
代码
#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;
}