[POI2010]MOS-Bridges


题目描述洛谷传送门LOJ 传送门思路好恶心好恶心的网络瘤题,属于是知道结论就会做但是会写挂的题,佩服出题人脑洞。性质:对于一条欧拉回路,每个点的入度 = 出度首先可以考虑二分答案,二分最小权值 xxx,对于每个 xxx,我们可以建出一张图来,在这张图中,我们把所有不符合条件的边砍掉(变成有向边,记得

[JSOI2016]飞机调度


JSOI 王国里有 $N$ 个机场,编号为 $1$ 到 $N$。从 $i$ 号机场到 $j$ 号机场需要飞行 $T_{i,j}$ 的时间。由于风向,地理位置和航空管制的因素,$T_{i,j}$ 和 $T_{j,i}$ 并不一定相同。 此外,由于飞机降落之后需要例行维修和加油。当一架飞机降落 $k$ 号机场时,需要花费 $P_k$​​ 的维护时间才能再次起飞。 JS Airways 一共运营 $M$ 条航线,其中第 $i$ 条直飞航线需要在 $D_i$ 时刻从 $X_i$ 机场起飞,不经停,飞往 $Y_i$ 机场。 为了简化问题,我们假设 JS Airway 可以在 $0$ 时刻在任意机场布置任意多架加油维护完毕的飞机;为了减少飞机的使用数,我们允许 JS Airways 增开任意多条临时航线以满足飞机的调度需求。 JYY 想知道,理论上 JS Airways 最少需要多少架飞机才能完成所有这 $M$ 个航班。

CF1082G Petya and Graph


题目描述题目传送门思路这道题和 [NOI2006] 最大获利 是一模一样的,做完记得去拿双倍经验这道题是一个经典的网络流模型:最大权闭合子图。先说做法:新建原点 $s$ 与汇点 $t$;将 $s$ 与图中每一个正权点相连,权值为该正权点点权;将 $t$ 与图中每一个负权点相连,权值为该负权点点权的绝