链式前向星

konyakest · 2025-06-17 19:17:25 · 个人记录

今天写了一个必须使用链式前向星，并且需要建两张图的题，然后调试发现好几处不分边的编号和点的编号，不分第一张图和第二张图的错误。

引以为戒。

以下指出链式前向星正确的使用方式：

struct Graph{
    struct Edge{int from,to,pre,nxt;}e[maxn*2];
    int h[maxn],edge_cnt=1;

    void add(int x,int y){
        e[++edge_cnt]={x,y,0,h[x]};
        e[h[x]].pre=edge_cnt;
        h[x]=edge_cnt;
    }

    void del(int id){
        e[e[id].pre].nxt=e[id].nxt;
        e[e[id].nxt].pre=e[id].pre;
        if(h[e[id].from]==id) h[e[id].from]=e[id].nxt;
    }

    template<typename T>
    void for_each(int u,T func){
        for(int eid=h[u];eid;eid=e[eid].nxt) func(e[eid].to,eid);
    }
}g1,g2;

使用（遍历所有 u 到 i 的，编号为 e 的边）：

g1.for_each(u,[&](int i,int e){
    // do something
});

不需要编号时可以这么写：

g1.for_each(u,[&](int i,int){
    // do something
});

既然这样，不如附上这题题解：

显然答案为 \max\{a\times dis_i,b \times \lfloor{dis_i\over 2}\rfloor+a\times (dis_i \bmod 2),b \times evendis_i\}

其中 evendis 表示只走 b 边的最短路。

考虑跑最短路。我们要解决的问题是：有两组点 a_i,b_i，有若干个（设为 k 个）表示不能走的边 (a_u,b_v)，我们需要在 dijkstra 时从 a 更新到 b。我们希望复杂度与 k 有关。

可以使用数据结构（类似可持久化线段树）暴力优化建图。但我们有更巧妙的做法：

还是考虑原图上这个问题的形式：a_i\to x\to b_i。此时，如果 x\to b_i 被访问过，则再次访问一定不会带来更好的更新。所有我们可以直接删掉。复杂度是 O(k)。

考虑这张图中这个结构的总和。发现是三元环的个数，为 O(n\sqrt n)。可以通过本题。