题意： n个岛屿，由m条桥连接，其中有k条是魔法桥，你可以用魔法把他们变成相同长度。 求在执行魔法后，两个起点S1和S2到终点T的最短路的最小绝对差。 （1≤n≤1000，1≤m≤2000，1≤k≤100） （1\leq n\leq 1000，1\leq m\leq 2000，1\leq k\leq 100） S1 S_1和 S2 S_2到 T T的最短路将会是如 j×x+disj\t

题目链接~~> 做题感悟：这题虽然看似很简单其实如果细心的话也不难，但是wa 了 n 次，wa 在了统计最优解个数上，开始没有开数组然后最后统计达到目标状态最优解的个数，这样是不对的，因为你只记录了最终的状态，可能在形成最优解的过程中有许多方法构成了最优解。 解题思路：                 (1) 、这题很容易想到状态方程 ： dp[ S ^ (1<<k) ] [ j ] [ k

题目链接：传送门 洛咕传送门 令 s u m w sumw sumw表示 w w w的前缀和。 显然的 d p dp dp方程： d p [ i ] = m i n ( d p [ j ] + ( h [ i ] − h [ j ] ) 2 + s u m w [ i − 1 ] − s u m w [ j ] ) dp[i]=min(dp[j]+(h[i]-h[j])^2+sumw[i-1]-

混合图的欧拉回路一般解法： 二分 + 最大流 先二分，然后判断该图是否能构成欧拉回路 考虑欧拉回路的成立条件，入度等于出度 也就是说，对于有向边，只用考虑其对入度出度的贡献， 然后对于无向边就要考虑其方向… 那么先任意规定无向边的方向，然后跑最大流。 在满足没有点出入度为0或出入度差为奇数（因为此时改变无向边的方向出入度之差变化为2）的前提下 如果能满流，那么就成立，否则不成立

E. Rudolf and k Bridges 这道题需要使用到deque deque:双端队列，可以在前后存取元素。 题目要求连续造k座桥，那么只需要把每一座桥的建造成本记录一下，最后取其中和最小的连续k座桥的成本即可。 对于每一座桥计算他的建造成本： 用dp来做，这座桥的第j个位置的建造成本为dp[j]; dp[j]=dp[k]+a[i][j]+1;其中k是一个范围[j-k-1,j-1]；

题目链接：HDUOJ 4738 Caocao’s Bridges 题目描述： 给定一个无向图，你可以选择最多删除一条边，删除边的代价是边的边权（特殊地，删除一条边权为0的边的代价是1），问最小代价使得图不连通。如果无论如何图都是连通的，那么则输出-1。 题解： 题目也就是需要我们求一条桥边，这个桥边所拥有的边权最小。我们只需要求出所有的桥边，然后对边权取一个最小值即可（需要注意边权为

描述 Caocao was defeated by Zhuge Liang and ZhouYu in the battle of Chibi. But he wouldn't give up. Caocao's army still was not good at water battles, so he came up with another idea. He built many isl