题解 P3640 【[APIO2013]出题人】

· · 题解

这道提答嘛……最短路和染色问题，先看最短路的几种算法（不管正确性与否）

Floyd 算法：裸Floyd，复杂度恒定\Theta(V^3)，与询问无关，没什么好说的。

优化的 Bellman-ford 算法：就是一个不变化跳循环而已，来个负权照样复杂度\Theta(QVE)。

改进的 Dijkstra 算法：用了堆优化，不过遇到负权就GG了。

第1/3个点：干Floyd：

Floyd是恒定\Theta(V^3)的，所以这么说来101个点就干掉了。

数据最小的话，没有边，刚好101+1+1+2=105个数，OK！

第2/5个点：干Bellman-ford：

复杂度\Theta(QVE)，来个负权，再来一堆自环/重边，人肉二分保证数据不超过T，且让Bellman-ford刚刚超过一丁点，就可以了，

第2个点要Floyd过，V=100即可，第5个点要Dijkstra过，那么就

0号点到299号点连正权边，其它点搞一堆负环+自环+重边，Bellman-ford轻松干掉。

第4/6个点：干Dijkstra：

说了Dijkstra看到负权就GG，所以构造一堆0边诱惑他，然后再让他从右边的点进去，举个栗子：

那么就先把它拐到4，发现路长为0，然后走2~3是最短的，拐到3，开始觉醒后，发现0~1再到2，路长为-2，再走2~3，傻傻地Dijkstra就被坑了，

这样多来几次就是指数级，卡卡常就可以了。

然后是染色问题：

Gamble1是恒过器，Gamble2是恒挂器，所以第7个点就是要算法T掉，第8个点就是要算法A掉。

第7个点来个完全图，那么多颜色估计染不到了。

第8个点——因为不能有重边——所以说，因为，所以就染2种颜色——蓝(男)色和绿(女)色。

那么每个蓝色点和绿色点连一条边，也就是说分成两组，同组之间不连边，异族之间连边，然后Recursive-Bactraking就过了。