Codeforces 724 E Goods transportation

Description

有 (n) 个点,每个点有一个入流和出流,每个点与编号比它大的点连边,容量为 (c) ,求最大流.

Sol

DP.

这种特殊的图可以DP,把最大流转化成最小割.

最小割就是 (sum s_i,iin S + sum p_j,j in T + c sum [i in S][jin T]) .

最后一个式子其实就是 (S) 与 (T) 的割边.

(f[i][j]) 表示前 (i) 个点有 (j) 个点 (in S)

转移就是对于一个点加入 (S) 还是加入 (T) 取 (min)

(f[i][j]=min{f[i][j-1]+s[i],f[i][j]+j*c+p[i]})

倒序枚举即可 复杂度 (O(frac {n(n-1)} {2}))

Code

#include<cstdio>
#include<iostream>
using namespace std;

typedef long long LL;
const int N = 10005;
const LL INF = 1LL<<60;

int n,c;LL ans;
int p[N],s[N];
LL f[N];

inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }
int main(){
	n=in(),c=in();
	for(int i=1;i<=n;i++) p[i]=in();
	for(int i=1;i<=n;i++) s[i]=in();
	for(int i=1;i<=n;i++) f[i]=INF;
	
	for(int i=1;i<=n;i++){
		for(int j=i;j;j--)
			f[j]=min(f[j-1]+s[i],f[j]+(LL)j*c+p[i]);
		f[0]+=p[i];
	}
	ans=INF;
	
//	for(int i=0;i<=n;i++) cout<<f[i]<<" ";cout<<endl;
	
	for(int i=0;i<=n;i++) ans=min(ans,f[i]);
	return cout<<ans<<endl,0;
}