[洛谷P3931]SAC E#1 - 一道难题 Tree
2024-09-17 02:24:39
题目大意:给你一棵带权有根树,可以切断一些边,问使得根和叶子节点不连通的最小代价。
题解:做了一天的网络流,这道题显然可以用最小割来做,但是也可以用树形$DP$,基本同[SDOI2011]消耗战,这道题一次询问,只需要那个$O(n)$的$DP$就行了。
卡点:无
C++ Code:
#include <algorithm>
#include <cstdio>
#define maxn 100010
const long long inf = 0x3f3f3f3f3f3f3f3f; int head[maxn], cnt;
struct Edge {
int to, nxt, w;
} e[maxn << 1];
inline void addedge(int a, int b, int c) {
e[++cnt] = (Edge) { b, head[a], c }; head[a] = cnt;
e[++cnt] = (Edge) { a, head[b], c }; head[b] = cnt;
} int n, rt, ind[maxn]; long long dfs(int u, int fa = 0) {
long long res = 0;
for (int i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if (v != fa) res += std::min(dfs(v, u), static_cast<long long> (e[i].w));
}
if (u != rt && ind[u] == 1) return inf;
return res;
} int main() {
scanf("%d%d", &n, &rt);
for (int i = 1, a, b, c; i < n; ++i) {
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
++ind[a], ++ind[b];
}
printf("%lld\n", dfs(rt));
return 0;
}
最新文章
- myeclipse 无法启动 java.lang.IllegalStateException: Unable to acquire application service. Ensure that the org.eclipse.core.runtime bundle is resolved and started (see config.ini).
- 标签语义化之常用HTML标签
- java基础介绍(转)
- SQLdiag-配置文件-ProfilerCollector
- FileDataSource java的文件操作
- 【经验】Windows7、8、8.1 MSI安装错误Error Code 2502 &; 2503 解决方法
- 怎么让自己的java系统使用支付接口
- 微信公众账号【iOSDevTip】推出新栏目【看大牛】
- BZOJ 2429: [HAOI2006]聪明的猴子
- Linux查看密码
- Android逆向破解表单注册程序
- net core体系-1概要
- vue项目目录结构
- 如何写出健壮的Java代码
- Effective C++ 第二版 31)局部对象引用和函数内new的指针 32)推迟变量定义
- 20145322 《网络对抗》 MSF基础应用1
- mock 测试 MVC
- vi下的查找替换命令
- Python 编码机制
- JBOSS在win7环境下启动run.bat无反应
热门文章
- Windows Server 2008 R2 安装域
- Spark性能优化--数据倾斜调优与shuffle调优
- 2019年猪年海报PSD模板-第五部分
- [JSON].value( keyPath )
- 谜题 (Puzzle,ACM/ICPC World Finals 1993,UVa227)
- python程序设计——函数设计与调用
- 对HashMap进行排序
- 数据库Mysql的学习(八)-储存过程和事务和导入导出
- 【Linux】Face Recognition的封装
- Map Reduce Application(Partitioninig/Binning)