给出n个工作的时间段，以及工作带来的价值，问工作k天，能得到的最大价值是多少
同poj 3680：n条线段，每条线段有价值，每条线段最多选k次，求选取到的最大价值是多少

先对线段的端点进行离散化，从每条线段的起点向终点连一条边，容量为1，费用为-w，。

对于相邻的两个时间点，从小的时间向大的时间连一条边，容量为k，费用为0，代表完成一个任务之后可以马上进行下一个任务，最多走k次。

最后s向每个时间点连一条边，表示每天可以从每个时间点开始，容量为k，费用为0

每个时间点向汇点连一条边，表示每天可以随时结束，容量为k，费用为0

因为每个时间点已经相通了，也可以直接连上s->最小的时间点，最大的时间点->t，容量为k，费用为0

最后求s到t的最小费用最大流，结果取反即为最大费用

3762 Accepted 6160K 1157MS G++ 3158B

继续阅读 →

“聊斋”中有这么一种随机图：
这个图只有一个入口和一个出口
在这个图中的所有边的方向都是确定的
这个图的入口的出度比入度大1：in[s] + 1 = out[s]
这个图的出口的入度比出度大1: out[s] + 1 = in[s]
图中除了出口和入口两个点，其余的点的入度等于出度 in[i] = out[i]

然后给了n个点m条边的有向图，入口标号s，出口标号t。
每条边有两个值a，b，如果保留这条边花费为a，删掉这条边的花费为b，问是否有最小花费把这个图变成随机图

建图的思想是贪心，图的样子有点像上下界的网络流：

首先对于每条边(u, v)，如果a > b表示不建这条边更合适，那么从v向u连一条边，容量为1，花费为a – b，sum += a
如果a < b，表示建这条边更合算，那么从u向v连一条边，容量为1，花费为b – a，sum += b，因为我们要了这条边，那么u的出度增加1，v的入度增加1：out[u]++，in[v]++；
这样，我们就用最小的花费把每条路都处理完了，但是这个图此时可能不满足除了花费最小以外的任何条件，接下来：
由t向s建一条边，容量为1，费用为0，  由t向s建一条虚拟边(?)这样我们只要把图中所有的点变成入度等于出度就可以了
新建S，T

• 对于每个点i，如果它的入度大于出度，为了增加他的出度，从i向T连一条边，容量为in[i] – out[i]代表这些流量跑满后这个点就平衡了

• 如果这个点的出度大于入度，就由S向i连一条边，容量为out[i] – in[i]，费用为0，代表流入这些流量后就平衡了

然后求一次从S到T的最小费用最大流，如果最大流等于所有in[i]的和，那么就是可能的，费用为sum + 最小费用

Accepted    4067    530MS    1564K    3331 B    G++

继续阅读 →