DP&图论 DAY 7 上午
图论练习题
P2176 [USACO14FEB]路障Roadblock
先跑最短路(最多n条边,否则出环)
枚举每条边,加倍,再跑 dijkstra
取最大
P2939 [USACO09FEB]改造路Revamping Trails
Solution
分层图最短路
从上一层到下一层,起点之间连边
Solution
暴力N^2建边
然后发现有一些边是没用的
假设存在3个点 (x1,y1) (x2,y2) (x3,y3)
min( |x1-x3| , |y1-y3| ) = x3-x1
--->min( |x1-x2| , |y1-y2| ) + min( |x2-x3| , |y2-y3| )
所以如果存在一条路径,st. point1--->point3 = point1-->point2 + point2-->point3
所以就把路径换成 1--2+2-->3 ,这样一定不会差
对于所有点,x从小到大排序,y从小到大排序,相邻两点之间连边,不允许跳点的跑路
跑最短路
P2502 [HAOI2006]旅行
Solution
。最小边越大,最大边也越大,不能满足二分性质
。枚举最小边,固定最小边,最小化最大边,最小生成树 kruscal
一开始 sort 一遍
枚举每个最小边,O(M) 克鲁斯卡尔
Solution
最近距离最远,可以二分
N^2连边
二分 mid ,边<mid,属于同一部落内部,看此时图中有多少连通块
数量<k,不可行,数量>=k,继续二分
MST
N^2连边
选若干条边,使得形成 K 个连通块,没选的边中最小值最大
只剩k个连通块,也就是剩下n-k条边,停止算法
kruscal
· Kruskal 最大生成树,加入 N − ne e d 条边就停止。
Solution
S表示前缀和,%2下
可以推理出S1~Sn
S0=0
S[R]----S[L-1]
传递性 x-->y y-->z ,x-->z
使得每个点都和0连通
加边,跑最小生成树
PS:奇偶异或,连通即可知
MST(最小生成树)
Solution
开到一个不是加油站的点,下一步最优去最近的加油站
以每个加油站为源点,跑多源多汇最短路
加油站转移
重构边,图上只留下加油站,忽略非加油站点,边权相应更改
也就是
也就是说:
Solution
Solution
真·不是二分
下面是不知道在讲啥子系列
Floyd + 倍增
接起来
快速幂加速
DP&图论 DAY 7 上午的更多相关文章
-
DP&;图论 DAY 6 上午
DP&图论 DAY 6 上午 双连通分量 从u-->v不存在必经边,点 点双连通分量 边双连通分量 点/边双连通分量缩点之后变成一个树 找连通块的时候不越过割点或者桥 P3469 [ ...
-
DP&;图论 DAY 5 上午
DP&图论 DAY 5 上午 POJ 1125 Stockbroker Grapevine 有 N 个股票经济人可以互相传递消息,他们之间存在一些单向的通信路径.现在有一个消息要由某个人开 ...
-
DP&;图论 DAY 4 上午
DP&图论 DAY 4 上午 概率与期望 概率◦某个事件A发生的可能性的大小,称之为事件A的概率,记作P(A).◦假设某事的所有可能结果有n种,每种结果都是等概率,事件A涵盖其中的m种,那 ...
-
DP&;图论 DAY 3 上午
DP&图论 DAY 3 上午 状态压缩dp >状态压缩dp ◦状态压缩是设计dp状态的一种方式.◦当普通的dp状态维数很多(或者说维数与输入数据有关),但每一维总量很少是,可以将多维 ...
-
DP&;图论 DAY 6 下午 考试
DP&图论 DAY 6 下午 考试 样例输入 样例输出 题解 >50 pt dij 跑暴力 (Floyd太慢了QWQ O(n^3)) 枚举每个点作为起点,dijks ...
-
DP&;图论 DAY 5 下午
DP&图论 DAY 5 下午 树链剖分 每一条边要么属于重链要么轻边 证明: https://www.cnblogs.com/sagitta/p/5660749.html 轻边重链都是交 ...
-
DP&;图论 DAY 4 下午图论
DP&图论 DAY 4 下午 后天考试不考二分图,双联通 考拓扑排序 图论 图的基本模型 边: 有向边构成有向图 无向边构成无向图 权值: 1.无权 2.点权 3.边权 4.负权(dij不 ...
-
DP&;图论 DAY 2 下午
DP&图论 DAY 2 下午 基础树形DP 前言◦ 1:与树或图的生成树相关的动态规划.◦ 2:以每棵子树为子结构,在父亲节点合并,注意树具有天然的子结构.这是很优美的很利于dp的.◦ 3 ...
-
DP&;图论 DAY 1 下午
DP&图论 DAY 1 下午 区间和序列上的DP 序列上的DP >序列上的dp状态设计最基本的形式 F[i]表示以 i 结尾的最优值或方案数.◦ F[i][k]表示以 i 结尾附加 ...
随机推荐
-
javascript中li标签的排序和数组sort的用法
<!DOCTYPE html> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <m ...
-
python核心编程-习题-第二章
PS:PDF在线地址:http://bcmi.sjtu.edu.cn/~zhaohai/ptm2012/data/Python-kernel.programming.v2.pdf 2-1 变量,pr ...
-
[置顶] 【cocos2d-x入门实战】微信飞机大战之三:飞机要起飞了
转载请表明地址:http://blog.csdn.net/jackystudio/article/details/11730601 不过明眼人一看就知道起飞的不是飞机,是背景,相对运动引起的错觉. 1 ...
-
centos6安装oracle时运行./runInstaller无法弹出图形界面
首先确保安装oracle的机器上安装了图形化界面. 1.利用xmanager登录到安装oracle的服务器上(直接用root用户登录) 2.运行 export DISPLAY=你的本机地址:0.0 3 ...
-
hdu 4135 a到b的范围中多少数与n互质(容斥)
Co-prime 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4135 input The first line on input contains ...
-
如何使用ASP.NET开发基于推技术的聊天室?
public class Content : System.Web.UI.Page{private void Page_Load(object sender, System.EventArgs e){ ...
-
SVN配置钩子
安装测试环境:109 CentOS4.6 安装: SVN1.32http://subversion.tigris.org/downloads/subversion-1.3.2.tar.gz安装:解压 ...
-
ssmWeb开发框架_2014-01
一直在准备做一套系统, 具体用来干什么都没确定. 只是从纯技术人员的想法, 先搭建一套开发的框架. 做的时候才发现, 系统用途不同, 框架也是不同的. 暂时就先当作企业内部管理的系统来做吧. 后台基础 ...
-
基于深度学习的中文语音识别系统框架(pluse)
目录 声学模型 GRU-CTC DFCNN DFSMN 语言模型 n-gram CBHG 数据集 本文搭建一个完整的中文语音识别系统,包括声学模型和语言模型,能够将输入的音频信号识别为汉字. 声学模型 ...
-
What is EJB
What is EJB 0.什么是EJB? 答:EJB是用于构建企业应用程序模块托管的.服务器端组件架构.EJB技术加速并简化了开发基于Java技术的分布式.事务性.安全和便携的应用程序. 先看一下E ...