link 首先我们要明白，floyed的本质上是一个dp，那么显然我们要先跑一边floyed，然后进行更新 当我们更新的两个点之间的距离的时候，显然我们改变的是和它们有关的距离，所以只要更新这两个边就可以了. #include<cstdio> #include<iostream> #include<cstring>…

[Jennie](P4180 [BJWC2010]严格次小生成树) 很显然，我们只要求出最小生成树以后，把没有用过的边插进去，然后删掉形成的环上的最大值就行了 因为要严格，所以我们还要记录一波次大值。 然后就是树上倍增的事情了。 #include<iostream> #include<cstdio> #include<…

Lisa 问题在于环，显然。 但是怎样建图才能把环搞出来呢？不能建无向图，而且男女要交错 那就一种情况男女，另一种女男 然后就是tarjan的事情了. #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #incl…

JennP3275 [SCOI2011]糖果e 差分约束到底在干什么？ 最短路的基本不等式是$dis_v<=dis_u+edge_i$ 那么要求最大的解要依据这个来建立起来一个图，跑最短路 求最小解要跑最长路，也就是 $dis_v>=dis_u+edge_i$ 然后跑最长路 #include<iostream> #inclu…

Lisa 用所有路径的长度的和除以所有路径的种类就可以了. #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; #def…