链式前向星

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

引以为戒。

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

CPP

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 的边）：

CPP

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

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

CPP

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)

。可以通过本题。

文章操作

相关推荐

评论

链式前向星