【HDU2018多校赛第十场】Videos
◇ 题目
<简要翻译>
有n个人以及m部电影，每个人都有一个快乐值。每场电影都有它的开始、结束时间和看了这部电影会得到的快乐值。电影分成两种类型，若同一个人连续（不是时间连续，是顺序连续）看了两部相同类型的电影，他的快乐值会扣除W，数据保证扣除的值不超过电影增加的快乐值。
特别的，一个人换电影不花费时间，即若第一部电影的结束时间等于下一部电影的开始时间，是可以两场都看的；看电影必须看完；一部电影只能一个人看。
<输入&输出>
输入包含多组数据，第一行为整数T表示数据组数。
每组数据第一行包含四个整数t,m,n,W，t表示电影结束的最晚时间不超过t，m表示电影的数量，n表示人的数量，W表示连续看相同类型的电影扣除的快乐值；接下来m行，每行描述一个电影，包含四个整数——s[i]、e[i]表示第i部电影的开始和结束时间，w[i]表示看第i部电影得到的快乐值，k[i]表示电影的类型，为0或1。
输出所有人的快乐值之和的最大值。
<样例&解释>
| Input | Output | Explain |
2 | 2000 1990 | 第一组数据只有一个人，依次看了 第1,2部电影； 第二组数据只有一个人，依次看了 第1,2部电影，但类型相同，扣除 10； |
◇ 解析
这道题是一道网络流的题……其中网络流的部分是队友不知道哪里找来的版，就不解释了QwQ
由于网络流的最大流无法处理多个人的情况，我们使用费用流，那么思路就非常清晰了——网络流中“流”的是人的个数，而费用就是每部电影的快乐值；
也就是说我们要求一个最大费用费用流，其实可以将所有边的费用取相反数，然后跑最小费用就可以了