问题

给个无相带权图，还有一个边的序列，A和B玩游戏，A可以选择边序列的某个前缀以某种代价加进图里，图确定下来之后B可以选择一些点。B的分数是他选的点权，A的分数是所有满足连着的两个点恰好有一个点被B选中的边权和-A添加边花费的代价。两个人都希望自己的分数-对方的分数最大。问你最终的分数。

思考

如果A没有办法修改图怎么做？

考虑B的方案，如果B选择了某个点会贡献点权的代价，如果B选择了某条边恰好某一端的点，就会贡献-边权的代价。

考虑网络流模型

考虑网络流最小割对于B来说每个点要么选要么不选，即 $x \in S$ 或 $x \in T$ ，S代表选的点，T代表不选的点。

每个点如果是正权就和S连一条边，负权和T连一条边。对于每条边，只需要把对应的点双向都连边就行了，这样一个选一个不选必定会割掉中间的边。由于是最小割，B的最优选择下就是当前答案-网络流贡献

加上修改考虑A的选择，每次其实是往图中加了一条边，直接在残余网络上加边跑就行了。最后的答案取最小值。

复杂度 $O (N^{2} M K)$ 这是理论复杂度上界，但实际上根本跑不满。

这题本来想卡每次重新建图的做法的，因为完全跑不满可以把数据出的再大很多。但是由于本人太菜不会分析网络流复杂度怕被喷，最后就干脆没卡。赛后被队友吐槽这个不是一眼经典模型题而且直接暴力跑网络流就过了TvT

结果 Poilog 和 Vltava 都没做这题，真是白瞎了。