赵嘉熠的博客

题目链接（洛谷）

题目大意

有$n$个城市$m$条道路，每条道路连接这$n$个城市中的某两个城市。任意城市之间最多只有一条道路相连。

这$m$条道路中有一部分为单向通行的道路，一部分为双向通行的道路。双向道路在统计时记为一条。

同一商品在不同城市价格$c$不同，但同一商品在城市中的买入和卖出价格是相同的。商人想要通过赚差价赚出旅费，且他只进行一次贸易，求最多能赚多少。

题目链接（洛谷）

题目大意

给出一个有$n$个节点$m$条边的无向图，节点编号为$1-n$，边编号为$1-m$。初始时小E同学在$1$号节点。数据可能包含重边和自环。

每条边都有一个妖怪住在边上。在节点$1$处有两种守护精灵A，B，每种都有无数个。无向图中每条边都有权值$a_i$和$b_i$，当且仅当小E身上携带的A守护精灵不少于$a_i$，且B守护精灵不少于$b_i$，这条边上的妖怪不会对通过这条边的人发起攻击。

求在不被妖怪袭击的情况下，到$n$号节点最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的个数与 B 型守护精灵的个数之和。

$2\le n \le 50000, 0\le m \le 100000, 1\le a_i,b_i \le 50000$

题目链接（洛谷）

题目大意

小a在一座雪山滑雪，这里分布着$m$条供滑行的轨道和$n$个轨道之间的交点（同时也是景点），而且每个景点都有一个编号$i$和一个高度$h_i$ 。给出每条轨道的长度$k_i$小a能从景点$i$滑到景点$j$当且仅当存在$i$和$j$之间的边，且$i$的高度不小于$j$。

题目链接（洛谷）

题目大意

有$n\le 150$个节点，节点之间有$m(m\le 5000)$条无向边，使得任意两个节点可以互相到达。

现在要去掉一条边，使得图中存在两个节点无法相互到达。

输出所有可以去掉的边。

题目链接（洛谷）

题目大意

有$n$个村庄，编号从$0$~$n−1$。给出$m$条双向公路连接这些村庄。

发生了一次地震，对所有村庄造成了一些损毁，但对公路没有影响。

现在要重建村庄，给出第$i$个村庄重建完成的时间$t_i$。之后又$Q$个询问$(x,y,t)$，对于每个询问。你要回答在第$t$天，从村庄$x$到村庄$y$的最短路长度为多少。如果无法找到路径或者$x,y$没有重建完成，输出$−1$。

$N\le 200,M\le \frac{N\times (N-1)}{2}, Q\le 50000$

题目链接（洛谷）

题目大意

给出一个$n$个节点$m$条边的图，求所有生成树中最大边权与最小边权差最小的，输出它们的差值。

$1\le n \le 100,1\le m\le \frac{n\times (n−1)}{2}$

题目链接（洛谷）

题目大意

有一座岛上有$n$个景点，从$1-n$编号，现在需要修公路将这些景点连接起来，可以修一级或二级的公路，一级公路的花费大于二级公路。

现在要修$n−1$条公路将景点连接，且在这$n−1$条公路中有$k$条是一级公路。

现给出$n,k$以及可以修的景点对和修一级公路和二级公路的花费。求满足要求的最小花费。

$1\le n \le 10000, k\le n−1,m\le 30000$

（题目链接）

题目大意

给出$n$个节点，编号为$0$~$n-1$，给出$m$条无向边。接下来给出包含$k$个数的数列$p$，$p_i$表示第$i$步要删除编号为$p_i$的节点。

求每一步图中连通块的个数

$1\le m \le 2\times 10^5, 1\le n\le 2\times m$

题目链接（洛谷）

题目大意

给出一些城市，从西向东排成一排，每个城市有一个海拔$h_i$，定义城市$i,j$间的距离位海拔之差的绝对值，即$d(i,j)=|h(i)-h(j)|$。

小$A$和小$B$轮流开车，第一天小$A$开车，之后每天换一次。他们计划选择一个城市$s$作为起点，一直向东，并且最多行驶$x$公里就结束旅行。

题目链接（洛谷）

题目大意

给定$n$个数，第$i$个数为$v_i$。

现在要把它分成数目之差不超过1的两部分，问这样的两部分数字和之差最小是多少？

$n \le 30$