Goods transportation

有 ?? 座城市，第 ?? 座城市会生产 ??_?? 商品，可以卖出 ??_?? 商品。

对于一对城市 ??,??(?? < ??)，?? 可以向 ?? 运输不超过 ??（对于所有 ??,?? 均相同）的商品。

求最多能卖出多少商品。

?? ≤ 10000。

题解

显然有一个网络流模型，源点向第 ?? 个点连容量为 ??_?? 的边，第 ?? 个点向汇点连容量为 ??_?? 的边，第 ?? 个点向第 ?? (?? < ??) 个点连容量为 ?? 的边，求个最大流。

但是跑得很慢。

考虑最大流等于最小割。

??[??][??] 表示前 ?? 个点，有 ?? 个点属于 ?? 集合的最小割为多少。

枚举第 ?? 个点属于 ?? 集还是 ?? 集转移。属于\(S\)集合只需要断它连向\(T\)的边，属于\(T\)集合不仅要断\(S\)连向它的边，还要断前面属于\(S\)集合的点连向它的边。

复杂度 ??(??²)。

CO int N=1e4+10;
CO int64 inf=1e18;
int64 c,s[N],t[N];
int64 dp[2][N];

int main(){
	int n=read<int>();
	read(c);
	for(int i=1;i<=n;++i) read(s[i]);
	for(int i=1;i<=n;++i) read(t[i]);
	for(int i=1;i<=n;++i){
		dp[i&1][0]=dp[(i-1)&1][0]+s[i],dp[i&1][i+1]=inf;
		for(int j=1;j<=i;++j)
			dp[i&1][j]=min(dp[(i-1)&1][j]+c*j+s[i],dp[(i-1)&1][j-1]+t[i]);
	}
	int64 ans=inf;
	for(int i=0;i<=n;++i) ans=min(ans,dp[n&1][i]);
	printf("%lld\n",ans);
	return 0;
}

CF724E Goods transportation

原文：https://www.cnblogs.com/autoint/p/12750912.html