2-SAT模板 说在前面 证明我还活着…… 每天做题做的疲于奔命, 高考课的作业又做不完。 啊啊啊啊 还有CSDN实在太**了,越来越**了,正在极慢速向cnblogs搬家。 天天高高兴兴打打模板 #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm&…

2018年9月10日 0条评论 2点热度 阅读全文

天天高高兴兴打打模板 #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; const int MAXN=100; const int MAXM=1000; const int INF=0x3f3f3f3f; int N,M; int Mix[MAXN…

2017年10月25日 0条评论 2点热度 阅读全文

Bellman-Ford算法 事先吐槽:几十年前的坑了!赶紧填完赶紧轻松 引子 有这样一类题,它要求你从某个点出发,到某个为止走过的最短路径。很早很早以前,我们学习了弗洛伊德算法与迪杰斯塔拉算法。 现在我们再来看看与前两种完全不同的做法。 算法原理与流程 Bellman-Ford算法的流程如下: 在图G(V, E)(V为点集,E为边集),取一源点s,数组Dis[i]记录从源点s到顶点i的路径长度,初始化Dis全清∞,Dis[s]为0; 以下操作循环执行至多n-1次,n为顶点数: 对于每一条边e(u, v),如果Di…

2017年5月15日 0条评论 2点热度 阅读全文

翻译成中文就是“松弛”,属于工程优化的范畴; Dijkstra 的单源最短路径算法,有一个重要的步奏,当访问到新的结点 u (加入到集合 S),然后遍历 u 的邻接顶点(Adj),如果经由该点 u 到达 v 的最短距离,比之前的估计距离(tentative distance)还要小,则进行更新(update),更新步便叫做,relaxation step。 for v in Adj(u): if d[v] > d[u] + weight(u, v): d[v] = d[u] + weight(u, v) u …

2016年9月3日 0条评论 3点热度 阅读全文