「Luogu P4389」[APIO2013]出题人

发表于 |
字数统计: 1k | 阅读时长 ≈ 5

题面不会解释。

链接

题解

前言

对于给出的三份$\texttt{SSSP}$的程序，考虑分析其时间复杂度。

$\texttt{Floyd:}$无论如何都是$O(n^3)$，与询问无关。

$\texttt{Dijkstra:}$搞了个堆优化，$O(n\log n)$，一上负权图就$\texttt{GG}$。

$\texttt{Bellman-Ford:}$一旦有负权照样退化成$O(qnm)$。

$\texttt{Subtask 1}$

卡$\texttt{Floyd}$，让$\texttt{Dijkstra}$过。

由于$\texttt{Floyd}$总是$O(n^3)$，所以考虑构造一个$101$个点的图，没有边，就可以卡掉了。

$\texttt{Subtask 2}$

卡$\texttt{Bellman-Ford}$，让$\texttt{Floyd}$过。

要让$\texttt{Floyd}$过，$n=100$即可。然后每个点随机连一些负权边，让$\texttt{Bellman-Ford}$不断的进行松弛操作，再带上$10$组询问就可以卡掉了。

这里我的策略是前$50$个点随机连$11$条边，后$50$个点随机连$10$条边，在这种随机图上很容易卡掉。

$\texttt{Subtask 3}$

跟$\texttt{Subtask 1}$一样。

$\texttt{Subtask 4}$

卡$\texttt{Dijkstra}$，让$\texttt{Floyd}$过。

先来看一个图：

这样一个图诱导$\texttt{Dijkstra}$走边权为$0$的边，走着走着就发现原来的那条不是最短路，就白白走了许多路径。用这种方法卡掉即可。

$\texttt{Subtask 5}$

卡$\texttt{Bellman-Ford}$，让$\texttt{Dijkstra}$过。

考虑到代码中的一个性质：每一次都是所有顶点进行松弛操作，而且只要有改变最短路就可以再松弛一遍，所以考虑构造一堆自己连向自己的负环，再在$0$和$1$之间连重边就可以卡掉啦qwq。

$\texttt{Subtask 6}$

只要你$\texttt{Subtask 4}$做得好的话，这个点也是一样的。

$\texttt{Subtask 7}$

染色问题，让你卡爆搜。

生成一个随机图就可以啦。

$\texttt{Subtask 8}$

让你构造数据使得爆搜通过。

考虑把点染色，异色的点之间连边，同色点之间不连边，于是就完了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=1e5+51;
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
} 
inline void hack1()
{
    puts("101");
    for(register int i=0;i<101;i++)
    {
    	puts("0");
    }
    puts("1\n1 100");
}
inline void hack2()
{
    ll edges;
    puts("100");
    for(register int i=0;i<100;i++)
    {
    	edges=i<50?11:10;
    	printf("%d ",edges);
    	for(register int j=0;j<edges;j++)
    	{
    		printf("%d %d ",rand()%100,-1);
    	}
    	puts("");
    }
    puts("10");
    for(register int i=0;i<10;i++)
    {
    	puts("0 99");
    }
}
inline void hack3()
{
    puts("101");
    for(register int i=0;i<101;i++)
    {
    	puts("0");
    }
    puts("1\n1 100");
}
inline void hack4()
{
    ll k=131072;
    puts("33");
    for(register int i=0;i<32;i++)
    {
    	if(i&1)
    	{
    	    printf("1 %d %d",i+1,-(k<<1)),k>>=1;
    	}
    	else
    	{
    	    printf("2 %d 0 %d %d",i+2,i+1,k);
    	}
    	puts("");
    }
    puts("0\n6");
    for(register int i=0;i<6;i++)
    {
    	puts("0 32");
    }
}
inline void hack5()
{
    puts("300\n1 1 1\n0");
    for(register int i=2;i<300;i++)
    {
    	printf("%d ",i<6?12:1);
    	for(register int j=0;j<(i<6?12:1);j++)
    	{
    		printf("%d -1 ",i);
    	}
    	puts("");
    }
    puts("10");
    for(register int i=0;i<10;i++)
    {
    	puts("0 1");
    }
}
inline void hack6()
{
    ll k=131072;
    puts("33");
    for(register int i=0;i<32;i++)
    {
    	if(i&1)
    	{
    	    printf("1 %d %d",i+1,-(k<<1)),k>>=1;
    	}
    	else
    	{
    	    printf("2 %d 0 %d %d",i+2,i+1,k);
        }
	    puts("");
    }
    puts("0\n6");
    for(register int i=0;i<6;i++)
    {
    	puts("0 32");
    }
}
inline void hack7()
{
    ll x,y;
    static ll vis[75][75];
    puts("71 1501");
    for(register int i=0;i<1501;i++)
    {
    	x=rand()%71,y=rand()%71;
    	while(vis[x][y]||x==y)
    	{
    	    x=rand()%71,y=rand()%71;
    	}
    	printf("%d %d\n",x,y),vis[x][y]=vis[y][x]=1;
    }
}
inline void hack8()
{
    ll x,y;
    static ll color[151],vis[151][151];
    puts("101 1501");
    for(register int i=0;i<101;i++)
    {
        color[i]=i%2;
    }
    for(register int i=0;i<1501;i++)
    {
    	x=rand()%101,y=rand()%101;
    	while(vis[x][y]||x==y||color[x]==color[y])
    	{
    	    x=rand()%101,y=rand()%101; 
    	}
        printf("%d %d\n",x,y),vis[x][y]=vis[y][x]=1;
    }
}   
int main()
{
}