GalenoJiao @ 2024-07-19 16:47:15
// 能过的代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n, m;
int g[MAXN][MAXN];// 用邻接矩阵不会重复建边 有向边 i->j表示i车站的等级高于j
int in[MAXN], si;
struct Node{// 拓扑排序的节点
int id, ord;
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n >> m;
bitset<MAXN> ext; // 1表示这次出现过,0表示这次没出现过
int st, ed, tmp;// 始发站、终点站
for(int i = 1; i<=m; ++i){
ext.reset();
cin >> si >> st;
ext[st] = 1;
for(int i = 1; i<si-1; ++i){
cin >> tmp;
ext[tmp] = 1;
}
cin >> ed;
ext[ed] = 1;
// 建边
for(int i = st; i<=ed; ++i){
if(!ext[i]){// 出现过的比没出现过的大
continue;
}
for(int j = st; j<ed; ++j){
if(ext[j] || g[i][j]){
continue;
}
g[i][j] = 1;
in[j]++;
}
}
}
queue<Node> q;
for(int i = 1; i<=n; ++i){
if(in[i]==0){
q.push(Node{i, 1});
}
}
int maxOrd = 1;// 最大拓扑序
while(!q.empty()){
Node u = q.front(); q.pop();
for(int i = 1; i<=n; ++i){
if(!g[u.id][i]) continue;
in[i]--;
if(in[i]==0){
q.push(Node{i, u.ord+1});
maxOrd = u.ord+1;// 晚入队的一定不比早入队的小
}
}
}
cout << maxOrd;
return 0;
}
为什么我把si和queue定义的位置改变一下,运行速度能有这么大差别啊。但是改变tmp就不会 (´・ω・`)? | si在全局 | si在主函数里 | |
---|---|---|---|
queue在全局,tmp在全局 | 1.70s | 1.82s | |
queue在全局,tmp在主函数 | 1.75s | 1.82s | |
queue在主函数,tmp在全局 | 1.36s | 1.78s | |
queue在主函数,tmp在主函数 | 1.35s | 1.81s |
我知道可能和编译器的优化有关,但是改变 si 位置对速度的影响这么大,而改变 tmp 位置却对速度几乎没有影响,我无法理解 (◎_◎)
有大佬能解释一下吗,非常感谢!
by Obijeb @ 2024-07-19 16:55:52
要不关掉O2再测一轮() @GalenoJiao
by YuzhenQin @ 2024-07-19 17:13:25
选择 C++14
提交都能通过,选择 C++14 (GCC9)
则 si
在主函数内无法通过。
使用 Compiler Explorer 发现当 si
在全局时,存储在寄存器里,在主函数内时,存储在栈里。
by GalenoJiao @ 2024-07-19 17:19:41
关掉O2 | si在全局 | si在主函数里 |
---|---|---|
queue在全局,tmp在全局 | 1.67s | 1.80s |
queue在全局,tmp在主函数 | 1.67s | 1.88s |
queue在主函数,tmp在全局 | 1.35s | 1.78s |
queue在主函数,tmp在主函数 | 1.35s | 1.82s |