网络流解决“同时做”问题模型
例题传送门：P2050 美食节
考虑从源点向每个要做的菜\(i\)连一条费用为\(0\)，流量为\(p_i\)的边
考虑建一层点，点\((j,k)\)表示第\(j\)个厨师做倒数第\(k\)道菜，则将每一个\((j,k)\)向汇点连一条费用为\(0\)，流量为\(1\)的边。
将菜\(i\)向\((j,k)\)连一条流量为\(1\)的边，因为倒数第\(k\)到菜只能做一道，思考费用：因为是厨师\(j\)做，所以是\(a_{i,j}\)，因为是倒数第\(k\)道菜，所以其贡献为\(k\times a_{i,j}\)，故费用为\(k\times a_{i,j}\)
理论上来说这样做就能解决“同时做”的模型了
但结合实际，在这道题上要优化：
我们发现，对于一个厨师来说，做倒数第\(k\)道菜之前一定要先做完倒数第\(k-1\)道菜，因为做倒数第\(k-1\)的费用永远比第\(k\)道小（看上面的费用计算）
所以我们先建部分点，为所有厨师做倒数第一道菜，即加入点\((j,1),j\in [1,m]\)，然后我们跑一条增广路，容易证明：该增广路上一定经过某个点形如\((j',1)\)，那么我们就可以加入\((j',2)\)，因为厨师\(j'\)已经做完倒数第一道菜，可以做倒数第二道菜了。直到新加入边后无法更新最大流（即已经流满时）退出循环。
上代码：
#include<bits/stdc++.h>
#define ll int
using namespace std;
const ll N=150,INF=1e9,M=1e6+50;
ll n,m,p[N],ti[N][N];
ll s,t,ans;
struct jgt
{
ll to,w,val,ne;
}e[M];
ll h[M],idx=1;
void add(ll x,ll y,ll z,ll v)
{
e[++idx].to=y;
e[idx].w=z;
e[idx].val=v;
e[idx].ne=h[x];
h[x]=idx;
e[++idx].to=x;
e[idx].w=-z;
e[idx].val=0;
e[idx].ne=h[y];
h[y]=idx;
}
ll cnt;
pair<ll,ll> dian[M];
ll now[M],net[M];
ll dis[M];
ll pre[M],liu[M],bian[M];
bool vis[M];
bool spfa()
{
memset(pre,0,sizeof pre);
for(ll i=0;i<=cnt;i++) dis[i]=INF;
dis[s]=0;
liu[s]=INF;
vis[s]=true;
queue<ll> q;
q.push(s);
while(!q.empty())
{
ll wz=q.front();
q.pop();
vis[wz]=false;
for(ll i=h[wz];i!=-1;i=e[i].ne)
{
ll j=e[i].to;
if(e[i].val&&dis[j]>dis[wz]+e[i].w)
{
dis[j]=dis[wz]+e[i].w;
bian[j]=i,liu[j]=min(e[i].val,liu[wz]);
pre[j]=wz;
if(!vis[j]) q.push(j),vis[j]=true;
}
}
}
if(dis[t]==INF) return false;
ans=ans+dis[t]*liu[t];
for(ll i=t;i!=s;i=pre[i])
{
e[bian[i]].val-=liu[t];
e[bian[i]^1].val+=liu[t];
if(i>n+1) net[dian[i].first]=max(net[dian[i].first],dian[i].second+1);//假如厨师j做了倒数第k道菜，那么考虑第k+1道菜是否已经加入网络流，若没有，则下面会更新
}
for(ll i=1;i<=m;i++)
{
if(net[i]>now[i])
{
now[i]=net[i];
dian[++cnt]={i,now[i]};
for(ll j=1;j<=n;j++)
add(j,cnt,ti[j][i]*now[i],1);
add(cnt,t,0,1);
}
}
return true;
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d %d",&n,&m);
s=0,t=n+1;
cnt=n+1;
for(ll i=1;i<=n;i++)
{
scanf("%d",&p[i]);
add(s,i,0,p[i]);
}
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++)
scanf("%d",&ti[i][j]);
for(ll i=1;i<=m;i++)
{
now[i]=1;
net[i]=1;
dian[++cnt]={i,1};//第i个厨师做倒数第1道菜
for(ll j=1;j<=n;j++)
add(j,cnt,ti[j][i],1);//倒数第1道菜为j的情况
add(cnt,t,0,1);
}
while(spfa());
printf("%d\n",ans);
return 0;
}