RainAir
My OI Blog
RainAir


文章归档

差分约束系统学习笔记

差分约束系统,就是给定一些 $ x_i - x_j >= d $ 的不等式,求出其中的一组解。我们可以转化为最短路来解决该类问题。 实现 PS:以下讨论整数情况,浮点数请注意精度。 我们对于每一组 $ x_i - x_j >= d $ 的不等式,从$ j $ 向 $ i $ 连一条长度为d的边。 可能有人…

   367   2018-03-17 去围观

「HNOI2009」最小圈

题目描述 题目分析 典型的01分数规划题目。 用来处理求平均值最小类的问题。 我们根据简单的转换,可以得出答案ans是可以二分的。 二分一个答案ans,我们把每个边权都减掉ans,再跑最短路,如果找到了一个负权环,那么说明ans不是最优。 最后:提醒大家注意精度…

   166   2018-03-17 去围观

强连通分量

概念 我们先来明确一些概念。 子图 图G=(V,E),G’=(V’,E’)中,若V’ ∈ V,E’ ∈ E,并且E’中的边所关联的顶点都在V’中,则称图G’是图G的子图 强连通性 对有向图G=(V,E)而言,若对于G中任意两个顶点Vi和Vj(Vi≠Vj ),都有一条从Vi到Vj的(有向路径),同时还有一…

   244   2018-03-17 去围观

分层图最短路

定义 分层图最短路问题,一般是指我们在可以进行分层的图上进行最短路。 一般模型是: 在图上,有k次机会可以直接通过一条边,问起点与终点之间的最短路径。 题目链接 分析 其实这一题我们用动态规划的思想看,用dist[i][k]表示免费了k次的最短路径 详细的转移请参…

   281   2018-03-11 去围观
文章归档