7277专题

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

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