landscaping专题

【DP】景观美化(Landscaping)

题目描述 题目: 农夫约翰最近决定来美化他的花园,他需要运输很多的泥土。花园是由N块花圃组成的。第i块花圃初始的时候有Ai数量的泥土。为了达到美化的目的,必须使得第i块花圃的泥土数量Ai变成Bi。 约翰有三个选择:第一,他可以买一个单位的泥土放进任意花圃中,代价是X;第二,他可以将一个单位的泥土从某一个花圃中除去,代价是Y;第三,他可以将第i块花圃中的一个单位的泥土搬运到第j块花圃中,大家是Z

Codeforces Gym 101128F (UVA Live 7277) Landscaping 最小割

题目传送门 给你一个地图,每一块分为高低两种,从高到低、低到高需要花a元,把一块从高改到低或者从低改到高需要b元。 问从上到下,从左到右遍历最少花多少钱。 对每条红线,要么跨越花a元,要么改造一块地花b元。 两种地形构成二分图。 源点连低地,汇点连高地,流量为b,表示改造地需要b元。 地图上相邻点之间连接,流量为a,表示跨越红线需要a元。由于不知道改造后哪些是高、哪些是低