APIO2013 TASKSAUTHOR 口胡

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

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