关于常数
  • 板块学术版
  • 楼主Francais_Drake
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/12/11 20:36
  • 上次更新2023/10/24 07:56:23
查看原帖
关于常数
546086
Francais_Drake楼主2022/12/11 20:36

在写费用流题目(二分图最大权匹配,点数 300300 边数 9×1049\times 10^4)的时候,发现之前有一份代码一直在 TLE,然后把边的存储方式从 struct 改成了数组(下面是两种实现的对比)

inline void Add(int x,int y,int e){
    E[++te]={y,e,h[x],1}; h[x]=te;
    E[++te]={x,-e,h[y],0}; h[y]=te;
} 
inline void Add(int x,int y,int e){
    to[++te]=y; ed[te]=e; nxt[te]=h[x]; fl[te]=1; h[x]=te;
    to[++te]=x; ed[te]=-e; nxt[te]=h[y]; h[y]=te;
} 

然后时间快了三分之一然后过了。请问这是为什么?(感觉如果在访问连续方面的话 struct 存边应该更快)

同时费用流 spfa 求最短路部分里面我把数组模拟的队列换成了 std::queue 也是快了几十毫秒。(但是感觉 std::queue 显然不可能优于数组)同样求问。

2022/12/11 20:36
加载中...