在写费用流题目(二分图最大权匹配,点数 300 边数 9×104)的时候,发现之前有一份代码一直在 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
显然不可能优于数组)同样求问。