DP&图论 DAY 7 上午

时间:2023-02-06 16:38:04

DP&图论  DAY 7  上午

图论练习题

DP&图论  DAY 7  上午

P2176 [USACO14FEB]路障Roadblock

DP&图论  DAY 7  上午

先跑最短路(最多n条边,否则出环)

枚举每条边,加倍,再跑 dijkstra

取最大

P2939 [USACO09FEB]改造路Revamping Trails

DP&图论  DAY 7  上午

Solution

分层图最短路

从上一层到下一层,起点之间连边

DP&图论  DAY 7  上午

DP&图论  DAY 7  上午

DP&图论  DAY 7  上午

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 ,这样一定不会差

DP&图论  DAY 7  上午

对于所有点,x从小到大排序,y从小到大排序,相邻两点之间连边,不允许跳点的跑路

跑最短路

DP&图论  DAY 7  上午

P2502 [HAOI2006]旅行

DP&图论  DAY 7  上午

Solution

。最小边越大,最大边也越大,不能满足二分性质

。枚举最小边,固定最小边,最小化最大边,最小生成树 kruscal

一开始 sort 一遍

枚举每个最小边,O(M) 克鲁斯卡尔

DP&图论  DAY 7  上午

DP&图论  DAY 7  上午

DP&图论  DAY 7  上午

Solution

最近距离最远,可以二分

N^2连边

二分 mid ,边<mid,属于同一部落内部,看此时图中有多少连通块

数量<k,不可行,数量>=k,继续二分

MST

N^2连边

选若干条边,使得形成 K 个连通块,没选的边中最小值最大

只剩k个连通块,也就是剩下n-k条边,停止算法

kruscal

· Kruskal 最大生成树,加入 N − ne e d 条边就停止。

DP&图论  DAY 7  上午

DP&图论  DAY 7  上午

Solution

S表示前缀和,%2下

可以推理出S1~Sn

S0=0

S[R]----S[L-1]

传递性  x-->y  y-->z ,x-->z

使得每个点都和0连通

加边,跑最小生成树

PS:奇偶异或,连通即可知

MST(最小生成树)

DP&图论  DAY 7  上午

DP&图论  DAY 7  上午

Solution

开到一个不是加油站的点,下一步最优去最近的加油站

以每个加油站为源点,跑多源多汇最短路

DP&图论  DAY 7  上午

加油站转移

重构边,图上只留下加油站,忽略非加油站点,边权相应更改

也就是

 枚举原图的边,如果两点最近加油站不同,就连边,把最近加油站连边

也就是说:

DP&图论  DAY 7  上午

DP&图论  DAY 7  上午

DP&图论  DAY 7  上午

Solution

DP&图论  DAY 7  上午

DP&图论  DAY 7  上午

DP&图论  DAY 7  上午

Solution

DP&图论  DAY 7  上午

迷一般的好题:file:///C:/Users/Administrator/Documents/Tencent%20Files/1296817027/FileRecv/Contention%20-%20Kick%20Start.htm

真·不是二分

DP&图论  DAY 7  上午


下面是不知道在讲啥子系列

线性基

Floyd + 倍增

DP&图论  DAY 7  上午

接起来

快速幂加速

DP&图论  DAY 7  上午

DP&图论 DAY 7 上午的更多相关文章

  1. DP&amp&semi;图论 DAY 6 上午

    DP&图论  DAY 6  上午 双连通分量 从u-->v不存在必经边,点 点双连通分量 边双连通分量 点/边双连通分量缩点之后变成一个树 找连通块的时候不越过割点或者桥 P3469 [ ...

  2. DP&amp&semi;图论 DAY 5 上午

    DP&图论  DAY 5  上午 POJ 1125 Stockbroker Grapevine 有 N 个股票经济人可以互相传递消息,他们之间存在一些单向的通信路径.现在有一个消息要由某个人开 ...

  3. DP&amp&semi;图论 DAY 4 上午

    DP&图论  DAY 4  上午 概率与期望 概率◦某个事件A发生的可能性的大小,称之为事件A的概率,记作P(A).◦假设某事的所有可能结果有n种,每种结果都是等概率,事件A涵盖其中的m种,那 ...

  4. DP&amp&semi;图论 DAY 3 上午

    DP&图论  DAY 3  上午 状态压缩dp >状态压缩dp ◦状态压缩是设计dp状态的一种方式.◦当普通的dp状态维数很多(或者说维数与输入数据有关),但每一维总量很少是,可以将多维 ...

  5. DP&amp&semi;图论 DAY 6 下午 考试

    DP&图论  DAY 6  下午  考试 样例输入 样例输出 题解 >50 pt      dij 跑暴力 (Floyd太慢了QWQ    O(n^3)) 枚举每个点作为起点,dijks ...

  6. DP&amp&semi;图论 DAY 5 下午

    DP&图论  DAY 5  下午 树链剖分  每一条边要么属于重链要么轻边 证明: https://www.cnblogs.com/sagitta/p/5660749.html 轻边重链都是交 ...

  7. DP&amp&semi;图论 DAY 4 下午图论

    DP&图论  DAY 4  下午 后天考试不考二分图,双联通 考拓扑排序 图论 图的基本模型 边: 有向边构成有向图 无向边构成无向图 权值: 1.无权 2.点权 3.边权 4.负权(dij不 ...

  8. DP&amp&semi;图论 DAY 2 下午

    DP&图论  DAY 2  下午 基础树形DP 前言◦ 1:与树或图的生成树相关的动态规划.◦ 2:以每棵子树为子结构,在父亲节点合并,注意树具有天然的子结构.这是很优美的很利于dp的.◦ 3 ...

  9. DP&amp&semi;图论 DAY 1 下午

    DP&图论  DAY 1  下午  区间和序列上的DP 序列上的DP >序列上的dp状态设计最基本的形式 F[i]表示以 i 结尾的最优值或方案数.◦ F[i][k]表示以 i 结尾附加 ...

随机推荐

  1. javascript中li标签的排序和数组sort的用法

    <!DOCTYPE html> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <m ...

  2. python核心编程-习题-第二章

    PS:PDF在线地址:http://bcmi.sjtu.edu.cn/~zhaohai/ptm2012/data/Python-kernel.programming.v2.pdf 2-1  变量,pr ...

  3. &lbrack;置顶&rsqb; 【cocos2d-x入门实战】微信飞机大战之三:飞机要起飞了

    转载请表明地址:http://blog.csdn.net/jackystudio/article/details/11730601 不过明眼人一看就知道起飞的不是飞机,是背景,相对运动引起的错觉. 1 ...

  4. centos6安装oracle时运行&period;&sol;runInstaller无法弹出图形界面

    首先确保安装oracle的机器上安装了图形化界面. 1.利用xmanager登录到安装oracle的服务器上(直接用root用户登录) 2.运行 export DISPLAY=你的本机地址:0.0 3 ...

  5. hdu 4135 a到b的范围中多少数与n互质(容斥)

    Co-prime 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4135 input The first line on input contains ...

  6. 如何使用ASP&period;NET开发基于推技术的聊天室?

    public class Content : System.Web.UI.Page{private void Page_Load(object sender, System.EventArgs e){ ...

  7. SVN配置钩子

    安装测试环境:109  CentOS4.6 安装: SVN1.32http://subversion.tigris.org/downloads/subversion-1.3.2.tar.gz安装:解压 ...

  8. ssmWeb开发框架&lowbar;2014-01

    一直在准备做一套系统, 具体用来干什么都没确定. 只是从纯技术人员的想法, 先搭建一套开发的框架. 做的时候才发现, 系统用途不同, 框架也是不同的. 暂时就先当作企业内部管理的系统来做吧. 后台基础 ...

  9. 基于深度学习的中文语音识别系统框架(pluse)

    目录 声学模型 GRU-CTC DFCNN DFSMN 语言模型 n-gram CBHG 数据集 本文搭建一个完整的中文语音识别系统,包括声学模型和语言模型,能够将输入的音频信号识别为汉字. 声学模型 ...

  10. What is EJB

    What is EJB 0.什么是EJB? 答:EJB是用于构建企业应用程序模块托管的.服务器端组件架构.EJB技术加速并简化了开发基于Java技术的分布式.事务性.安全和便携的应用程序. 先看一下E ...