正权边卡SPFA的基本思路是弄一个网格图,然后这个网格图行比列小得多,比如10*10000之类的…
然后对于竖着的边边权就设多么小,然后横着的边权就设多么大(比如1和rand()%10000+10)
还可以在图里随机加一些奇怪的边.
然后对于点个数1e5,边个数2e5的有向图,随机打乱边或随机打乱边+SLF的SPFA都被卡到了入队1e8次…
PS:
可以将横着的边权构造一下,说不定就可以卡得更大了…
发现随机边权模数不一样差别很大.
另外还有说什么把网格图搞成立方体图不知道会怎么样(因为升了一维嘛…)
代码可以参考一下:这份代码至少可以卡到入队8e7以上
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
| #include<bits/stdc++.h>
using namespace std;
struct edge{int u,v,w;};
vector<edge>v;
int id[5000][5000],n=9,tp,m=42866/n,a[1000000];
int r(){
return rand();
}
int main(){
freopen("in.txt","w",stdout);
srand(time(0));
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
id[i][j]=++tp,a[tp]=tp;
int SIZE=29989;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
if(i<n){
v.push_back(edge{id[i][j],id[i+1][j],1});
v.push_back(edge{id[i+1][j],id[i][j],1});
if(j<m){
if(1)v.push_back(edge{id[i][j],id[i+1][j+1],r()%SIZE+10});
else v.push_back(edge{id[i+1][j+1],id[i][j],r()%SIZE+10});
}
}
if(j<m){
v.push_back(edge{id[i][j],id[i][j+1],r()%SIZE+10});
v.push_back(edge{id[i][j+1],id[i][j],r()%SIZE+10});
}
}
fprintf(stderr,"[%d,%d,%d]",v.size(),n,m);
random_shuffle(v.begin(),v.end());
printf("%d %d\n",tp,v.size());
for(int i=0;i<v.size();++i)printf("%d %d %d\n",a[v[i].u],a[v[i].v],v[i].w);
}
|
upd:发现一种奇妙的SPFA优化:每次将进队多次的点放到队首,可以过掉这种数据…
然而这个优化可以被一个最naive的数据卡掉…即
addedge(1,i,2*(n-i+1)+1),addedge(i,i-1,1),然后将这些边打乱后输出
这个也是最原始的卡SPFA方法,不加SLF的SPFA可以被这个卡掉
1
2
3
4
5
6
7
8
9
| #include<bits/stdc++.h>
using namespace std;
int main(){
freopen("spfa6.out","w",stdout);
int n=99999,m=199996;
printf("%d %d\n",n,m);
for(int i=n;i>=2;--i)
printf("1 %d %d\n%d %d 1\n",i,(n-i+1)*2+1,i,i-1);
}
|
