题解 洛谷 P3640 【[APIO2013]出题人】

一道有意思的题答构造题。题目是要你卡掉一个算法,给另一个算法过。前 6 个点是最短路的三种解法,后面 2 个点是一个染色问题。


最短路部分

一些需要了解的东西:

  • FloydWarshall 就是 \(O(V^3)\),和边无关。

  • ModifiedDijkstra 堆优化的 Dijkstra,正权图里 \(O(Q*\log V*E)\),负权图可以卡。

  • OptimizedBellmanFord \(O(QVE)\),随机图跑的快。

然后就可以开始了。

一、卡掉 Floyd (Task1,3)

最简单的部分,可以直接令 \(V=101,E=0\),Floyd 正好炸开。此时 \(T=105\),正好满足限制。

cout << "101" << endl;
for (int i=1;i<=101;i++) cout << "0" << endl;
cout << "1\n1 101\n";

二、卡掉 BellmanFord (Task2,5)

从这里本题正式开始。BellmanFord 可以用负环卡掉,或者是用自环和重边等。

  • 给 Floyd 过(Task 2)

    即为 \(n\le100\)。卡掉 BellmanFord 我造了几组自环和重边,一条从 \(99\) 到 \(1\) 的大长链,然后调了半天,终于把这个点卡了。

    cout << "100" << endl;
    int tot=1100;
    for (int i=0;i<100;i++) 
    {
    	if (i!=0);
    	else 
    	{
    		cout << "1 0 13\n";
    		continue;
    	}
    	int u=min(tot,30)/2;
    	cout << u+5 << " ";
    	for (int j=1;j<=u;j++) cout << i << " " << rand()<<" ";
    	if (tot>30) tot-=30;
    	else tot=0;
    	cout << i-1 << " " <<rand()-rand()<<" ";
    	cout << i-1 << " " <<rand()-rand()<<" ";
    	cout << i-1 << " " <<rand()-rand()<<" ";
    	cout << i-1 << " " <<rand()-rand()<<" ";
    	cout << i-1 << " " <<rand()-rand()<<" ";
    	cout << endl;
    }
    cout << "10" << endl;
    for (int i=1;i<=10;i++) cout << "99 0\n";
    
  • 给 Dijkstra 过(Task 5)

    考虑负环。由于题目要求起点开始无负环,所以可以将起点终点从用偶数点连,奇数点做负数自环。稍微卡一下就行了。

    cout << "300" << endl;
    for (int i=0;i<300;i++) 
    {
    	if (i%2==0)
    	{
    		if (i==298) 
    		{
    			cout << "0" << endl;
    			continue;
    		}
    		cout << "1 " << i+2 << " 1 " << endl; 
    	}
    	else
    	{
    		if (i>80) cout << "1 " << i << " -1 " << endl; 
    		else cout << "2 " << i << " -1 " << i << " -1 "<< endl; 
    	}
    }
    cout << "10" << endl;
    for (int i=1;i<=10;i++) cout << "0 298\n";
    

三、卡掉 Dijkstra (Task4,6)

这里是最难的。我们知道 Dijkstra 在负权图上可能被卡掉。那么怎么卡呢?我去看了题解,这里给出一种构造方法。

题解 洛谷 P3640 【[APIO2013]出题人】

每个三角形是前一个三角形边权 \(2\) 倍。构造若干个这样的三角形结构,这样傻傻的 dij 会已知沿着 \(0\) 的边走到 \(0\),然后往回走,这样就是指数级的。

然后给出 Task 4 的代码,Task 6 几乎一样,减少一下询问数即可。

cout << "33" << endl;
int tot=1;
for (int i=0;i<33;i++) 
{
	if (i==0) 
	{
		cout << "0\n";
		continue;
	}
	if (i%2==0)
	{
		printf("2 %d %d %d %d\n",i-2,0,i-1,2*tot);
	}
	else printf("1 %d %d\n",i-1,-4*tot);
	if (i%2==0)
	{
		tot*=2;
	}
}
cout << "10" << endl;
for (int i=1;i<=10;i++) cout << "32 0\n";

最短路部分到此结束。


染色问题部分

先观察三个代码。

  • RecursiveBacktracking 爆搜。

  • Gamble1 永远不会 TLE。

  • Gamble2 永远都会 TLE。

所以两个问题就是要你卡掉爆搜和给爆搜过。这部分不难。

结合 \(T\),你会发现边数是固定为 \(1501\) 的。

一、卡掉 RecursiveBacktracking (Task7)

众所周知,爆搜随便卡。然后搞个随机图就可以了。这个代码好像不用给吧。

二、给 RecursiveBacktracking 过 (Task8)

因为边数固定,点数又不能小,考虑答案 \(X=2\)。然后这就是一个二分图,直接构造一个二分图就可以过了。这个代码好像也不用给吧。


本题综合考察了对三个最短路的理解和掌握和图论知识,是个不错又奇怪的题。

我的做题记录:

题解 洛谷 P3640 【[APIO2013]出题人】

上一篇:POJ3268 - Silver Cow Party - Dijkstra跑两遍最短路


下一篇:最短路径-迪杰斯特拉(Dijkstra)算法