APIO2013 TASKSAUTHOR 口胡

r_64 posted @ 2015年12月03日 05:36 in 未分类 , 875 阅读

实在做不动UR7的B题就先把这个原版的做了吧

【1】构造 $V=101$ 的空图即可。 $105$ 个数。

【2】观察OptimizedBellmanFord，发现它的更新是按点的编号顺序的，我们就按照点的编号逆序做成一条 $V\to 0$ 的链，其中有重边，一共 $E$ 条边。询问 $V\to 0$ 十遍，就可以把它的复杂度卡到 $O(VE)$ 。 $counter=10(V-1)E$ ，数的个数为 $24+2E+V$ 。取 $V=100,E=1011$ 可以卡掉BellmanFord且只有 $2146$ 个数。

【3】也是 $V=101$ 的空图。 $105$ 个数。

【4】因为题目允许负权边，所以可以考虑这样的构图：

在这张图上，dijkstra的 $counter$ 是指数级的。计算参数： $V=2n+1$ ， $E=3n$ ， $2+2Q+V+2E\le 161$ 。令 $Q=1,n=19$ ，可以卡掉Dijkstra，用了 $157$ 个数。

【5】大致同【2】。 $10VE\ge 10^6,24+V+2E\le 1016$ 。取 $V=300,E=335$ 即可。使用了 $994$ 个数。

【6】大致同【4】。运行时间是 $Q(3\times 2^n-2)$ 。限制是 $2Q+8n+3\le 143$ 。发现 $Q=6,n=16$ 满足条件，使用了 $143$ 个数。

【7】我们从参数中可以知道，满足要求的图一定是 $E=1501$ 的。我们需要构造一个色数尽量大的图，构造一个完全图一样的东西即可。

【8】要求色数尽量小，构造一个二分图即可。