幻影彭的彩虹

记录青春的扇区

0%

坑

发表于 更新于

多测的奇妙问题

最短路

你清空了吗？

你真的清空了吗？

你真的真的真的清空了吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dij(int s,int t){
	memset(vis,0,sizeof(vis));
	memset(dis,1,sizeof(dis));
	//while(!q.empty())q.pop();
	dis[s]=0;q.push(s);
	while(!q.empty()){
		int u=q.top()%M;q.pop();
		if(vis[u])continue;vis[u]=1;
		if(vis[t])return ;
        //!!! priority_queue 还没空就跑路了，你不玩完谁玩完
		for(int i=head[u];~i;i=a[i].next){
			int v=a[i].v,w=a[i].w;
			if(dis[u]+w>=dis[v])continue;
			dis[v]=dis[u]+w;
			q.push(dis[v]*M+v);
		}
	}
}

一些迷惑问题

Prim 最短路

1
2
3
4
5
6
7
for(i=1;i<=n;i++){
    int tar=0;
    for(j=1;j<=n;j++)if(dis[tar]>dis[j]&&!pd[j])tar=j;
    pd[tar]=1;ans+=dis[tar];dis[tar]=0;
    for(j=1;j<=n;j++)cmin(dis[j],dis[tar]+val[tar][j]+val[j][tar]);
    //	for(j=1;j<=n;j++)if(!pd[j])cmin(dis[j],dis[tar]+val[tar][j]+val[j][tar]);
}

你的边权算对了吗？

有人之前写的 Prime 算法

匿名函数排序

1
2
sort(b+1,b+m+1,[](int a,int b){return a<b;});
sort(b+1,b+m+1,[](int a,int b){return b>a;});

你的排序，是这个升序的，还是这个降序的，还是这个无序的。

线段去包含

思考清楚到底怎么排序，如果右端点相同，按什么排序。

端点会不会是负数，maxn 初始值会不会太大（开 0，结果有线段端点是 0 你把它干了）

需要记录一些原来编号的排序

想清楚排序得到的 rk 数组到底是什么，不要乱查乱用，该求逆的求逆。

一些技巧的坑

非显式建边

举个例子，点有个性质 $c_i$，可以花费 $k_j$ 的代价从任意 $c_{a_j}$ 的跳到任意 $c_{b_j}$ 的点。

然后你对每个 $c$ 建立一个点，从每个点向它连了一条边。

然后你发现你的每一个 $c$ 可以花费 $0$ 的代价互相到达。

正确的方式是每个 $c$ 建立入点和出点。

可删除的优先队列

一般用两个优先队列实现，需要保证被删除的元素一定存在。

语言本身的坑

cerr

调试的时候 cerr 很好用的，就算忘了删也不会爆零，但是 cerr 真的很慢，因为它直接向标准输出流输出了，没有过缓冲区，相当于每次输出一次就 fflush(out) 一下，TLE 没商量。