回归梦想

题解

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2)

/ 注册

全部文章 / 题解（共270篇）

[USACO09FEB]Revamping Trails G

题意：约翰一共有 N 个牧场.由 MM 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 1 出发到牧场 N 去给奶牛检查身体。通过每条小径都需要消耗一定的时间。约翰打算升级其中 K 条小径，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 0。请帮助约...

** 分层图

2021-01-18

0 767

CG的通关秘籍

题意： n次顺序填数字，每次填一个[1,m]的数到当前位置，如果这个位置填的数比上一次填的数要大，形成顺序，他的兴奋度会增加1点，如果这个数比上一次填的数要小，形成逆序，他的兴奋度会增加2点，如果两个数相等，那么什么都不会发生。（如果是第一次填数，同样不会发生任何事情）已知n和m求所以填数方案的兴奋...

ing 数论思维

2021-01-16

3 599

NC19939 [CQOI2015]网络吞吐量

NC19939 [CQOI2015]网络吞吐量题目： • 路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路...

最短路网络流

2021-01-15

0 801

NC51319 King's Quest

NC51319 King's Quest 题目： N个男生和N个女生，告诉你每个男生喜欢的女生编号，然后给出一个初始匹配（这个初始匹配是一个完美匹配），求在保证匹配是完美匹配的基础上，输出每个男生可能会匹配的女生题解：参考题解：让我们首先来考虑建图如果王子u喜欢妹子v那我们可以从u向v连一条有...

****

2021-01-14

0 865

NC20099 [HNOI2012]矿场搭建来自专栏

NC20099 [HNOI2012]矿场搭建题目： • 煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。• 于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。•...

**** tarjan 割点

2021-01-14

0 755

NC51307 Redundant Paths

NC51307 Redundant Paths 题目： • 给定无向连通图，求至少需要添加几条边使它变成一个边双连通图。（添多少边可以消灭所有的桥）题解：先用边双连通缩点• 缩点之后是一棵树• 无根树的叶子（度数为1的点）都需要再添一条边，叶子节点两两连接• 答案是是（叶子数+1）/2 代码：...

** tarjan 缩点

2021-01-14

0 527

NC106972 Cow Ski Area

NC106972 Cow Ski Area 题目： • N*M的滑雪场，每个点都有他的高度，滑雪的时候只能向四周相邻的不高于当前点的高度的点滑，现在滑雪场准备修建若干个缆车线路，使得奶牛可以从任意一个点运动到滑雪场的每个点，问最少需要建多少条缆车线路。题解：本质还是有向图，通过加边使其强连通• ...

** tarjan 缩点

2021-01-14

0 575

NC51269 Network of Schools

NC51269 Network of Schools 题目：给你一张有向图，问最少要加几条边才能使得图上的点都属于同一个强连通分量题解：加边变成强连通分量缩点之后，入度为0的点和出度为0的点两两连边，多随便一连——答案就是max（入度为0的点数，出度为0的点数）处理后：代码： #inclu...

** tarjan 缩点

2021-01-14

0 640

NC50403 [ZJOI2004]嗅探器

NC50403 嗅探器题目： • 某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络，蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息，但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。现在需要你尽快...

*** tarjan 割点

2021-01-14

1 795

NC20603 [ZJOI2007]最大半连通子图

NC20603 [ZJOI2007]最大半连通子图题目： • 一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：u,v∈V，满足u→v或v→u，即对于图中任意两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。• 若G'=(V',E')满足V'∈V，E'是E...

拓扑排序 **** tarjan 缩点

2021-01-14

0 732