威风镰鼬

题解

/ 注册

全部文章 / 题解（共6篇）

题解 | #[NOIP2017]棋盘#

思路没啥思考过程，照着题目跑bfs就过了。大概就是跑的时候记格子的花费和是否用过魔法。记录颜色时+1是因为比较方便区分白色。剪枝直接把同一格子花费大的剪掉就行了。正确性的大概考虑：若经过同一格子两次，用魔法的状态肯定是一样的，并且金币只会递增。（不知所云）代码 #include<bits/...

搜索 NOIP 普及组 bfs 最短路

2021-08-06

2 424

题解 | #[SDOI2009]ELAXIA的路线#

思路通过求出dis的交集来得到公共路径。然后重新建一个图。对x1，y1,x2,y2分别进行一次求最短路，交集部分（点的dis相同）进行rebuild，生成一个可拓扑排序求最长路径的DAG.因为做了课件，代码的注释写得很详细，这里就不细讲了。题解 #include <bits/stdc++....

最短路图论拓扑排序

2021-07-28

1 563

题解 | #小木乃伊到我家#

思路写一个Dijkstra堆优化的模板供大家参考一下。（码风比较丑，不要介意）代码 #include<bits/stdc++.h> using namespace std; const int maxn=200005,maxm=500005; struct E{ int n...

最短路 dijkstra

2021-06-15

1 445

题解 | #[USACO 2009 Oct G]Heat Wave#

思路这道题很开放，spfa能过、Dijkstra能过，普通求法（见代码）也能过。这边供上一个Dijkstra堆优化板子求最短路。坑点：注意优先队列默认是从大到小的，重载运算符要写a.dis>b.dis，别把堆优化做成堆劣化。 Dijkstral代码 #include<bits/stdc...

最短路普及组图论

2021-06-13

1 658

题解 | #挖沟#

思路与<15108道路建设>同解，Kruskal硬过就行了。代码 #include<bits/stdc++.h> using namespace std; const int maxn=100005,maxm=1000005; struct E{ int fro...

普及组最短路 Kruskal 图论

2021-06-12

1 477

题解 | #[NOIP2014]寻找道路#

[NOIP2014]寻找道路思路首先要把一些不满足条件的点剔除掉，然后就是求最短路的事情了。要找不满足条件的点，可以反向建边，然后从终点出发，标记每一个经过的点。那么剩下没有走过的点就可以去掉了。代码 #include<bits/stdc++.h> using namespace ...

最短路提高组图论 NOIP bfs

2021-06-09

1 694