漫话最小割 part1

 

codeforces 724D

[n个城市每个城市有一个特产的产出,一个特产的最大需求。当i<j时,城市i可以运最多C个特产到j。求所有城市可以满足最大的需求和]

[如果直接最大流建图显然会T。考虑将最大流问题转换为最小割。每个城市会被划分到S集或者T集。]

[另dp[i][j]表示前i个城市有j个城市在S集的最大和。

dp(i, j) = min(dp(i - 1, j - 1) + si, dp(i - 1, j) + pi + j * c).

[将网络流转化为最小割,并用DP加以解决]

 

 

HDU 4971

[经典题变形: 有n个项目有收益,m个投资有花费。每个项目需要完成若干个投资,同时投资直接也有依赖关系]

[我们可以将收益先取走,将收益也转化为花费。S向项目连边,投资向T连边,流量都是对应花费。依赖关系的流量为INF。最小割即为答案]

 

 

Codechef SPCLN

[n个发射器,m个陨石。每个发射器可以打一些陨石并有收益。陨石被打直接有依赖关系,n个发射器依次发射。求最大收益]

[每个陨石用n+1个点的链表示,流量依次为每个发射器的花费(那个陨石拿100收益,多出来的为花费),如果打不了就是INF。S连向第一个点,最后一个点连向T。陨石i依赖j,则在i的链的第k个连向j的链的k+1,流量为INF,最小割为答案]

 

 

[观察上面两个问题的特点。]

[1.有花费也有收益。对于收益,我们应该将其转化为花费以便最小割问题解决。单个物品的转换比较简单,先获得收益,再把收益变为花费。多个物品的转换,可以选择一个足够大的值获得,再把这个值减去收益变为花费。]

[2.有依赖关系。在还有收益的模型里依赖关系非常好理解,如果你想要获得这个好处,你必须blabla。但应该我们将收益转化为花费,依赖关系就会变为这几个代价,你至少要挑一个承受。]

[由1,2。我们得到一个一般的最小割建模思路。首先将问题转换成若干个事件,每个事件有一个花费。有一些事件间的关系,每一个关系可以表述为:这些事件必须至少发生一件,或者,这些事件不能全不发生。于是我们可以用边刻画事件,流量为费用,如果不能发生就是INF。每一个关系我们将这些事件从S连到T。为了刻画关系更加方便,用INF的边单纯表示事件连接,分为或连接蕴含连接或连接的实际意义是如果该连接之前的事件没有发生,则之后必须发生一件。蕴含连接的实际意义是如果该连接之前的事件发生,则之后得事件也要发生。两种连接的方式分别是尾连头,头连头]

[经过总结,我们得出一个结论。什么样的问题可以用最小割解决呢?逻辑上只包括或关系或者蕴含关系]

原文地址:https://www.cnblogs.com/jszkc/p/7310257.html