APIO2013 TASKSAUTHOR 题解

题目描述

解法分析

要区分两个程序 $A$ 和 $B$，就要知道 $A$ 和 $B$ 各自的优缺点.

1. SSSP

FloydWarshall 的运行效率取决于点数 $V$，通过代码可以发现 $\mathrm{counter}=V^3$，与询问数 $Q$ 无关.

OptimizedBellmanFord 通过多轮松弛求出最短路，从代码中可以看出，每轮按照边在输入文件中的顺序松弛，当 $s$ 出发的最短路恰好沿着输入边的顺序时，一轮松弛就能求出最短路，但如果恰好逆着这个顺序，则要松弛 $V-1$ 次才能求出最短路.

ModifiedDijkstra 当边权均为正时就是复杂度有保证的 Dijkstra 算法，而当有负边权时类似贪心的 SPFA. 不难发现当从 $s$ 出发的最短路第一条边不是 $s$ 边权最小的出边时，可能有大量无用的松弛操作.

2. Mystery

Gamble 为题目设计所用，不考虑.

RecursiveBacktracking 为暴力迭代深搜求解图的色数的程序，复杂度指数级，随便的图就能使其 TLE，要使其不 TLE 就要构造答案接近于程序的枚举顺序的图.

详细题解

测试点1

问题为 SSSP，$A$ 为 ModifiedDijkstra，$B$ 为 FloydWarshall，$T=107$.

要使 FloydWarshall 程序 TLE，只需令 $\mathrm{counter}=V^3>10^6$，即 $V>100$. 由于输入文件不能包含超过 $107$ 个数，只要生成 $V=101$ 的空图（没有边）以及任意 $1$ 组询问即可.

测试点2

问题为 SSSP，$A$ 为 FloydWarshall，$B$ 为 OptimizedBellmanFord，$T=2222$.

显然 FloydWarshall 通过的条件是 $\mathrm{counter}=V^3\le 10^6$，即 $V\le 100$，因此可取 $V=100$. 因为输入一条边有 $2$ 个整数，所以图 $G$ 的边数应当在 $E=1100$ 左右. 在此基础上要使 OptimizedBellmanFord 程序 TLE，应使最短路逆着松弛顺序，这样 $\mathrm{counter}$ 约等于 $VEQ=1.1\times 10^6$.

最简单的方法就是构造从点 $99$ 到点 $0$ 最短路 $99,98,...,1,0$，为增加边数，每个点 $i$ 往前连 $11$ 条边 $(i,i-1),(i,i-2),...,(i,i-11)$，但只有 $(i,i-1)$ 出现在最短路上，这可通过控制边权得到（以下是伪代码）：

for(int i=99;i>=0;i--){
    int n=(i>11?11:i);
    for(int j=1;j<=n;j++)link(i,i-j,j*j);
}

其中 link(i,j,w) 表示连边 $(i,j)$，权值为 $w$. $10$ 组询问均为 $s=99$，$t=0$ 即可.

测试点3

问题为 SSSP，$A$ 为 OptimizedBellmanFord，$B$ 为 FloydWarshall，$T=105$.

测试点3与测试点1类似，事实上，直接使用之前测试点1构造的图即可通过测试点3.

测试点4

问题为 SSSP，$A$ 为 FloydWarshall，$B$ 为 ModifiedDijkstra，$T=157$.

$T$ 很小意味着点数和边数都不能太大，也就是说要将 $B$ 的复杂度卡到指数级.

只有 $G$ 中有负边权，ModifiedDijkstra 才会出现 $s$ 的边权最小的出边不在最短路上的情况，这样才能使其做大量无用的松弛操作，如下图：

      -1   -2
    0 -> 1 -> 2
 -2 |         | -2
    v         v
    3 -> 4 -> 5
      -1   -1

起点 $s=0$，终点 $t=5$，则 ModifiedDijkstra 就会按照 $0,3,4,5$ 顺序加入优先队列松弛（此时 dist[5]=-4），接着队首为 $1$（dist[1]=-1），再按照 $1,2,5$ 顺序松弛（此时 dist[5]=-5）.

如果有 $k$ 个这样的子图串联，那么可以得到 $2^k$ 条不同的路径，通过合理设置边权即可使所有的路径都走一遍. 为了减少边数，图按如下方式简化：

    -2      -2      -2      -2
 0 ----> 2 ----> 4 ----> 6 ----> 8
  \    -* \    -* \    -* \    -*
 -1\|  /|-1\|  /|-1\|  /|-1\|  /|
   -* /-9  -* /-5  -* /-3  -* /-2
     1       3       5       7

每个子图为 $(i,i+1)$，$(i,i+2)$，$(i+1,i+2)$三条边，边权指数级递减，就能保证每次更新 dist[t] 都会减少.

设有 $k$ 个这样的子图，则点数为 $2k+1$，边数为 $3k$，询问数 $Q=10$时，输入文件中数的个数为 $1+2k+1+2\cdot 3k+1+20=8k+22$，由 $8k+22\le 157$ 得 $k\le 16$，因此将 $16$ 个这样的子图串联即可（以下是伪代码）：

for(int i=0,w=-32768;i<32;i+=2,w/=2){
    link(i,i+1,-1);
    link(i,i+2,-2);
    link(i+1,i+2,w-1);
}

$10$ 组询问均为 $s=0$，$t=32$ 即可.

测试点5

问题为 SSSP，$A$ 为 ModifiedDijkstra，$B$ 为 OptimizedBellmanFord，$T=1016$.

ModifiedDijkstra 对于大多数的图 $G$，运行效率都很高，所以关键在于使 OptimizedBellmanFord 程序 TLE。

当 $Q=10$ 时，设边数为 $E$，则输入数的个数为 $1+V+2E+1+20=V+2E+22$，而 OptimizedBellmanFord 的最坏情况下 $\mathrm{counter}=(V-1)E$，由基本不等式 $\frac{V-1+2E}{2}\ge\sqrt{2E(V-1)}$，因此在输入数的个数一定时，要使 $\mathrm{counter}$ 最大，则 $V-1=2E$. 然而这样边数不足点数，实际可达的点不足 $V$，无法令程序复杂度达到最坏情况.

因此可以令 $E=V-1$，并将所有点连成一个链. 注意题目要求 $V\le 300$，所以可以构造链 $299,298,297...,0$. 输入还没满，可以再加一些不在最短路上的边（伪代码如下）：

for(int i=1;i<300;i++){
    link(i,i-1,1);
    if(i>=255)link(i,i-2,4);
}

$10$ 组询问均为 $s=299$，$t=0$ 即可.

测试点6

SSSP，$A$ 为 OptimizedBellmanFord，$B$ 为 ModifiedDijkstra，$T=143$.

测试点4构造的图可以使 $A$ 通过，唯一的问题在于输入数的个数超过了限制.

但经过测试可以发现，测试点4构造的图 ModifiedDijkstra 只处理 $6$ 组询问就会 TLE，所以将询问数减少为 $6$ 组即可通过该测试点.

测试点7

问题为 Mystery，$A$ 为 Gamble1，$B$ 为 RecursiveBacktracking，$T=3004$.

这是一个送分点，任意生成一个 $V=71$，$E=1501$ 的稠密图基本上就能令 $B$ 程序 TLE.

测试点8

问题为 Mystery，$A$ 为 RecursiveBacktracking，$B$ 为 Gamble2，$T=3004$.

~~首先明确数据范围，只能是 $V=71$，$E=1501$，这样输入文件恰好包含 $3004$ 个数.~~

要让迭代深搜通过，不难想到要使答案 $X$ 尽可能小，也就是 $X=2$，然而这样的图无法构出，这是因为，设编号为 $0$ 和 $1$ 的点数分别为 $n_1$ 和 $n_2$ 个，则边数 $E\le n_1n_2$，由基本不等式 $E\le n_1n_2\le (\frac{n_1+n_2}{2})^2=(\frac{71}{2})^2<1501$.

（感谢r_64提醒，上面的说法是错的……以下是本人的逗比做法）

所以我们考虑构造一个 $X=3$ 的图.

为了让 $A$ 通过，第一步 $A$ 在尝试 $X=2$ 时需要较快地退出，我们可以构造一个编号较小的三元环 $0,1,2$，即连边 $(0,1)(1,2)(2,0)$.

接着尝试 $X=3$，我们把编号在 $[3,70]$ 之间的点分为 $3$ 组，所有的边 $(i,j)$ 满足 $i$ 和 $j$ 不在同一组，第一步程序确定 $0,1,2$ 的编号分别为 $0,1,2$ 后，程序将会先将第一组的点标号为 $0$，再将第二组的点标号为 $1$，最后将第三组的点标号为 $2$. 这样就不会回溯了（伪代码如下）：

link(0,1);
link(1,2);
link(2,0);
int m=1498;
for(int i=3;i<25&&m;i++){
    for(int j=26;j<50&&m;j++){
        for(int k=51;k<71&&m;k++){
            link(i,j);m--;
            if(m)link(j,k),m--;
            if(m)link(i,k),m--;
        }
    }
}

其中 link(i,j) 为连边 $(i,j)$.

UPDATE：Mystery 问题与 SSSP 的输入方式不同，输入规模只和 $E$ 有关，和 $V$ 无关，所以令 $V=78$ 就能构造二分图（即 $X=2$ 的图）了（伪代码如下）：

int m=1501;
for(int i=0;i<39&&m;i++){
    for(int j=39;j<78&&m;j++){
        link(i,j);m--;
    }
}

总结

本题的 $8$ 个测试点构造的程序都很短，难点在于构造不容易想到. 构造的关键在于发现不同算法的优劣之处，这样就能针对算法在某些特殊情况下的缺陷生成特定的数据使程序 TLE.

WrongAnswer的博客

博客