P1315 [NOIP2011 提高组] 观光公交

小h什么是氮气加速器？有知道的可以告诉我一下。

小h这道题一看就是贪心，但是我对费用流更熟悉，而且数据量不大，因此可以用费用流。更好理解一点。

我们定义3个1维数组：Mx、down和tim，分别代表景点i游客最晚到达时间、该景点下车的人数和公交不用氮气加速器时的到达时间。这时，只要把每一个游客的下车时间减去到达等车地点的时间，即为不用氮气加速器时的总等待时间。

这道题里面，最小费用代表相比不用氮气加速器，用了之后可以省多少时间。当然，省的时间肯定越多越好，那样就是最大费用了，用不了模版了。想要用昨天那个模版，可以把费用设为负数。最大流代表使用了多少氮气加速器。

建图。定义超级源点S和超级汇点T，定义S1，连接一条Ｓ到S1的有向边，费用是0，流量为K，用来限制N2O加速器的个数。把一个景点i劈开，变成i和i+n，这是费用流的常见操作。然后从S1向i+n连接费用为0，流量为D（i）的有向边，用来分配加速器。时间不能小于0，所以流量是D（i）。从i向超级汇点连一条流量为无穷、费用0的有向边，用来收集总共省的时间。从i+n向i+1连一条有向边，流量无穷，费用为-down（i+1）用来计算省的时间，传递先前加速器对后面的影响。

接下来是重点。连接i到i+n的有向边，费用0，流量max(tim[i] - Mx[i], 0)，用来传递i以前的加速器对后面的影响。如果前面用的加速器大于tim[i] - Mx[i]个，到后面只有tim[i] - Mx[i]个的影响会体现出来。比如：3个车站，1到2用时12分钟，2到3用时12分钟，有100个加速器，有一个人在10分钟时到达2，则1到2哪怕使用了更多加速器，也只有2个影响到此人。

发现节点1和n*2没用，建图时可以忽略。

还不懂的就耐心画一下图。

正解defineINF 0x3f3f3f3f defineN 100005 struct peo { int t, l, r; } a[N]; int D[N], Mx[N], down[N], tim[N], S, T; int main() { int n, m, K, i, ans = 0; scanf("%d%d%d", &n, &m, &K); for (i = 1; i < n; i++) scanf("%d", &D[i]); for (i = 1; i <= m; i++) { scanf("%d%d%d", &a[i].t, &a[i].l, &a[i].r); down[a[i].r]++; Mx[a[i].l] = max(Mx[a[i].l], a[i].t); } for (i = 1; i < n; i++) tim[i + 1] = max(tim[i], Mx[i]) + D[i]; for (i = 1; i <= m; i++) ans += tim[a[i].r] - a[i].t; S = n * 2 + 1; T = n * 2 + 3; int S1 = n * 2 + 2; MFMC.s = S; MFMC.t = T; MFMC.n = T; MFMC.addE(S, S1, K, 0); for (i = 1; i < n; i++) { MFMC.addE(i, i + n, max(tim[i] - Mx[i], 0), 0); MFMC.addE(i + n, i + 1, INF, -down[i + 1]); MFMC.addE(S1, i + n, D[i], 0); MFMC.addE(i + 1, T, INF, 0); } MFMC.check(); printf("%d\n", ans + MFMC.what().second); return 0; }

正解以上为核心代码，完整版应在开头加上昨天提供的费用流模版。

小h复杂度玄学，但是能过。不建议这样做。

正解