突发奇想做一道非传统题。。。
只要发现这些算法的一些性质就好了:
SSSP:
FloydWarshall:稳定(O(V^3))
ModifiedDijkstra:正权图跑得贼快,负权图可能会被卡掉
OptimizedBellmanFord:时间按复杂度取决于更新节点的顺序
Mystery(染色问题):
RecursiveBacktracking:时间复杂度很大程度上取决于答案的大小
Task1
既然ModifiedDijkstra在正权图上跑得飞快,我们只需要构造正权图卡掉FloydWarshall即可。
由于FloydWarshall是稳定(V^3)的,只要出到(V>100)就行了,所有点的出边数量可以为0。
(允许的话甚至可以没有询问,但是本题要求(Q>0))
code:
#include<bits/stdc++.h>
using namespace std;
int n=101;
int main(){
freopen("1.txt","w",stdout),printf("%d
",n);
for(int i=1;i<=n;++i)puts("0");
puts("1
1 1");
return 0;
}
Task2
由于FloydWarshall稳定(V^3),我们考虑让(V=100),这样FloydWarshall永远也不会被卡掉,又给我们卡OptimizedBellmanFord提供了最方便的条件。
发现OptimizedBellmanFord是(O(V^2E))的,但是由于剪枝的存在,可能跑不满。
如何让它跑满呢?
发现它更新节点的顺序是从0到(V-1),所以我们只需要建一条链,(V-1)为起点,0为终点就好了。
但是还不够,由于点数有限,导致链的长度有限,而且给定的(T)远远没用完。
那么把剩下的(T)建成重边就好了。
code:
#include<bits/stdc++.h>
using namespace std;
int n=100,T=2222,Q=10,Num,RE,RN;
void print(int x){
if(x!=n-1){
printf("%d ",Num);
for(int i=1;i<=Num;++i)printf("%d 1 ",x?x-1:n-1);//0与n-1之间的边并不会影响复杂度
puts("");
}else{
printf("%d ",Num+RE);
for(int i=1;i<=Num+RE;++i)printf("%d 1 ",x?x-1:n-1);
puts("");
}
}
int main(){
freopen("2.txt","w",stdout);
printf("%d
",n),T-=1+n+1+(Q<<1),Num=(T>>1)/n,RE=(T>>1)-Num*n;
for(int i=0;i<n;++i)print(i);
printf("%d
",Q);
while(Q--)printf("%d 0
",n-1);
return 0;
}
Task3
由于FloydWarshall稳定(V^3),直接令(V>100)就可以直接卡掉,放OptimizedBellmanFord过也很简单,不连边就好了。
code:
#include<bits/stdc++.h>
using namespace std;
int n=101;
int main(){
freopen("3.txt","w",stdout);
printf("%d
",n);
for(int i=1;i<=n;++i)puts("0");
puts("1
0 1");
return 0;
}
Task4
我们说过ModifiedDijkstra在负权图上可能被卡掉。
那么怎么建负权图呢?
建立如下图的结构就好了。
这样的话每次ModifiedDijkstra会先沿边权为0的边更新偶数编号的节点,然后从小到大更新奇数编号的节点,然后从奇数编号的节点更新偶数编号的节点,又重新开始更新偶数编号的节点,更新结束以后才又开始更新下一个奇数编号的节点,时间复杂度变为指数级别。
具体建立多少个点,进行几次询问呢?
先假设我们尽可能建点,建立(2x+1)个点,那么就需要建立(3x)条边。
得(1+(2x+1)+(2 imes 3x)+1+2=157)
解释一下:1是输出(V)的数量,(2x+1)是输出(n_i)的数量,(3x)是输出边的数量,由于要用两个数字表示一条边所以要乘2,(1)是输出(Q)的数量,由于至少要有1个询问,所以2是输出询问的数量。
解得(x=19),则(V=39),显然不会把FloydWarshall卡掉。
但是我们发现这么写并不能让ModifiedDijkstra T掉,但是已经很接近了。
我们发现当我们减少两个点,建出的图就会少2个点3条边,也就少输出了8个数,可以让我们添加4次询问。
于是我们令(V=37,Q=5),成功让ModifiedDijkstra T掉。
code:
#include<bits/stdc++.h>
using namespace std;
int n=37,q=5,tt=1;
int main(){
freopen("4.txt","w",stdout);
printf("%d
",n);
puts("0");
for(int i=1;i<n;++i)i&1?printf("1 %d %d
",i-1,-tt<<1):(printf("2 %d 0 %d %d
",i-2,i-1,tt),tt<<=1);
printf("%d
",q);
for(int i=1;i<=q;++i)printf("%d 0
",n-1);
return 0;
}
Task5
类似Task2,建正权边即可。
不过还没完,这次的(T)要小一些。
不过如果像我这么写也很方便,直接把Task2的代码中的(n)改成300,(T)改成1016即可。
code:
#include<bits/stdc++.h>
using namespace std;
int n=300,T=1016,Q=10,Num,RE,RN;
void print(int x){
if(x!=n-1){
printf("%d ",Num);
for(int i=1;i<=Num;++i)printf("%d 1 ",x?x-1:n-1);
puts("");
}else{
printf("%d ",Num+RE);
for(int i=1;i<=Num+RE;++i)printf("%d 1 ",x?x-1:n-1);
puts("");
}
}
int main(){
freopen("5.txt","w",stdout);
printf("%d
",n),T-=1+n+1+(Q<<1),Num=(T>>1)/n,RE=(T>>1)-Num*n;
for(int i=0;i<n;++i)print(i);
printf("%d
",Q);
while(Q--)printf("%d 0
",n-1);
return 0;
}
Task6
会了Task4的话这里也很简单了。
由于(T)减少了14,那么我们可以减少4个点(减少了16个输出的数字),相应地增加1个询问(增加了2个输出的数字)就好了。
并不用管OptimizedBellmanFord,绝对卡不掉的。
code:
#include<bits/stdc++.h>
using namespace std;
int n=33,q=6,tt=1;
int main(){
freopen("6.txt","w",stdout);
printf("%d
",n);
puts("0");
for(int i=1;i<n;++i)i&1?printf("1 %d %d
",i-1,-tt<<1):(printf("2 %d 0 %d %d
",i-2,i-1,tt),tt<<=1);
printf("%d
",q);
for(int i=1;i<=q;++i)printf("%d 0
",n-1);
return 0;
}
Task7
由于RecursiveBacktracking的时间复杂度与(X)的答案有很大关联,(X)变大的话时间复杂度就会骤然上升,所以相当于我们要构建一个(X)很大的图。
考虑构建完全图。
得(2+V(V-1)=3004),2是输出(V,E)的数量,(V)个点的完全图有(frac{V(V-1)}{2})条边,需要用(V(V-1))个数表示。
解得(lfloor V floor=55)。
但是数据要求(V>70)。
突然想到我们建完55个点的完全图以后,不是还有多余的(T)吗?
发现多余的(T)是32,可以建16条边,而16条边刚好将节点54到70连成一条链。
code:
#include<bits/stdc++.h>
using namespace std;
int n=71,gr=55,E=1501;
int main(){
freopen("7.txt","w",stdout);
printf("%d %d
",n,E);
for(int i=0;i<gr;++i)for(int j=i+1;j<gr;++j)printf("%d %d
",i,j);
for(int i=gr;i<n;++i)printf("%d %d
",i-1,i);
return 0;
}
Task8
同Task7,我们考虑建立(X)尽可能小的图。
发现(X)最小的图就是链,(X=2)。
然而我们尴尬地发现(V<1000,E>1500),并不能建成链。
那怎么办?
我们令(V=999),先连成一条链,再将剩余的边连在标号相差2的节点之间就好了。
这样建出的图(X=3)。
code:
#include<bits/stdc++.h>
using namespace std;
int n=999,E=1501;
int main(){
freopen("8.txt","w",stdout);
printf("%d %d
",n,E);
for(int i=1;i<n;++i)printf("%d %d
",i-1,i),--E;
for(int i=0;i<n&&E;++i)printf("%d %d
",i,i+2),--E;
return 0;
}