APIO2013 TASKSAUTHOR 口胡

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

实在做不动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】要求色数尽量小,构造一个二分图即可。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter