摘要：
原题链接：https://www.luogu.com.cn/problem/P3387 题意解读：求一条路径，使路径经过的点权值之和最大，路径上点可以重复但每个点权值只算一次，输出最大的权值和。 解题思路： 1、问题分析 如果是DAG，可以直接通过拓扑排序来进行递推，计算到每个点的路径权值之和的最大 阅读全文
posted @ 2025-04-28 16:00
hackerchef
阅读(62)
评论(0)
推荐(0)
摘要：
原题链接：P2863 [USACO06JAN] The Cow Prom S 题意解读：有向图的强联通分量模版题。 解题思路： 一、强连通性概念 强连通性是图论中描述有向图顶点间关系的重要概念。对于有向图 G=(V,E)： 强连通：如果图中任意两个顶点 u 和 v 之间存在从 u 到 v 的路径，也 阅读全文
posted @ 2025-04-28 15:06
hackerchef
阅读(194)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/CF1120D 题意解读：在一颗树中，每个节点u都可以对其子树所有叶子节点增加一个数x(x可以是正、负、0)，每个节点i的操作都有代价c[u]，假定叶子节点初始设置为任意值，求选择哪些节点做操作，可以使得叶子节点值都变成0， 阅读全文
posted @ 2025-04-24 21:54
hackerchef
阅读(93)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P3623 题意解读：n个节点m条边的无向图，其中边有两种类似，一种是“水泥路”，一种是“鹅卵石路”，要求一种生成树方案，正好将n个节点连通，且“鹅卵石路”条数正好是k条。 解题思路： 1、问题分析 由于限制鹅卵石路的条数， 阅读全文
posted @ 2025-04-23 10:18
hackerchef
阅读(39)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/CF1245D 题意解读：给n个城市供电，每个城市有坐标(x,y)，给城市i直接供电花费是c[i]，通过一个有电的城市i给没电的城市j供电花费是 (k[i]+k[j]) * (|x1-x2|+|y1-y2|)，求最少的花费， 阅读全文
posted @ 2025-04-22 09:59
hackerchef
阅读(57)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P2700 题意解读：n个节点n-1条边的带权图，其中有k个节点标记为敌军，删掉一些边，使得k个敌军节点互补连通，求删除的边权值之和最小值。 解题思路： 1、问题分析 换一个角度，要求删除多少边使得k个节点互不连通，不如在一 阅读全文
posted @ 2025-04-22 09:03
hackerchef
阅读(58)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P1967 题意解读：在n个节点的带权无向图中，有q个询问，求两点之间的路径中，最小边的最大值。 解题思路： 1、初步分析 要求两点之间路径中最小边的最大值，可以将kruskal算法变化一下： 从大到小一次处理每条边，当将边 阅读全文
posted @ 2025-04-21 17:39
hackerchef
阅读(57)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P1550 题意解读：挖n个井，每个井i直接挖的代价是w[i]，如果从一个已有井i挖一条路到j，则开通井j的代价是p[i][j]，求挖所有井的最小代价。 解题思路： 井可以看做图中的节点，直接挖的代价是点权值，从已开通的井挖 阅读全文
posted @ 2025-04-21 12:11
hackerchef
阅读(56)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P1195 题意解读：在图中选择若干边，构成k个连通块时，求所选择的边的最小权值和。 解题思路： 在kruskal算法中，从小到大枚举每条边u->v，加入并查集使得u->v之间连通，计算连通块达到k个时，此时所选择的所有边权 阅读全文
posted @ 2025-04-21 11:41
hackerchef
阅读(51)
评论(0)
推荐(0)
摘要：
原题链接：https://www.luogu.com.cn/problem/P1396 题意解读：找到一条从s到t的路径，使得最大边权值最小，求这个最大的边权值。 解题思路： 根据kruskal的算法模型，对边权值小到大处理的过程，如果加入某条边权后，出现s、t连通，那么最后一次的边权即s到t路径上 阅读全文
posted @ 2025-04-21 11:08
hackerchef
阅读(45)
评论(0)
推荐(0)
浙公网安备 33010602011771号