什
by Rainy7 @ 2020-07-05 16:59:32
第一眼：哦要卡别人。
第二眼：等等这题题目好眼熟
第三眼：..我做过。
危 我 危
by Rainy7 @ 2020-07-05 17:00:24
能够无意义回复吗？
by zzyhzyy @ 2020-07-05 17:03:28
这题我之前用队列的spfa加了写玄学优化过的
后来在另一个题才发现那玄学优化是有问题的，过不去
by suxxsfe @ 2020-07-05 17:10:09
卡 DFS-SPFA 的数据生成器要来了（狂喜
by Retired_Doubeecat @ 2020-07-05 17:38:27
@[StudyingFather](/user/22030)
```
#include<bits/stdc++.h>
using namespace std;
int main(){
struct Edge{int s , t , w;}; vector < Edge > Ed1 , Ed2; int N , sum = 0; cin >> N; bool flag; cin >> flag;
mt19937 rnd(time(0));
vector < int > tms_pot; tms_pot.resize(N);
for(int i = 0 , tms = 2048 ; 2 * i < N ; ++i){tms_pot[i] = tms_pot[N - 1 - i] = tms; if(i > N / 3) tms >>= 1;}
for(int i = 1 , c = 1 ; c <= N ; i += 3 , ++c){
bool f = rnd() % 2;
Ed2.push_back((Edge){i , i + 1 , f ? 1500 : 2500 + tms_pot[c - 1]});
Ed2.push_back((Edge){i + 1 , i + 3 , f ? 2500 + tms_pot[c - 1] : 1500});
Ed2.push_back((Edge){i , i + 2 , 2000});
Ed2.push_back((Edge){i + 2 , i + 3 , 2000});
if(flag ^ (i >= N / 2)) reverse(Ed2.end() - 4 , Ed2.end());
sum += 4000;
}
for(int i = 3 * N + 1 ; sum >= 0 ; ++i)
if(sum >= 5000){Ed1.push_back((Edge){i , i + 1 , -5000}); sum -= 5000;}
else{Ed1.push_back((Edge){i , 1 , -sum - 1}); sum = -1;}
cout << Ed1.back().s << ' ' << Ed1.size() + Ed2.size() << endl;
for(auto t : Ed1) cout << 1 << ' ' << t.s << ' ' << t.t << ' ' << -t.w << endl;
for(auto t : Ed2) cout << 2 << ' ' << t.t << ' ' << t.s << ' ' << t.w << endl;
return 0;
}
```
不会卡到指数只会卡到三方 /kk
食用方法：输入整数 $N(1 \leq N \leq 1000)$ 和 $flag$ 表示边序（为了分别卡链式前向星和 vector）
大概能把 dfs_spfa 卡到 $O(n^2v)$ 的样子
@[Job_Lee](/user/114181) 的代码输出的是两个 Yes 但答案是两个 No 不知道是怎么回事= =
by Itst @ 2020-07-06 10:12:26
@[Itst](/user/96296) 请问spfa+SLF优化会被卡吗?
by 墨舞灵纯 @ 2020-07-06 10:48:09
@[墨舞灵纯](/user/87724)
这个 gen 是用来专门卡 dfs-spfa 的，我没试过 slf 会不会死……
但是 slf 当然可以卡啊 awa ~~只是我懒得卡了~~
by Itst @ 2020-07-06 10:55:24
@[Itst](/user/96296) 谢谢！（话说slf怎么卡啊qwq
by 墨舞灵纯 @ 2020-07-06 11:12:08
前排兜售北京烤鸭~
by syanoeclipse @ 2020-07-06 17:25:58