【POJ】1935 Journey(树形dp)

时间:2022-09-18 16:19:33

题目

传送门:QWQ

分析

凉凉。

答案是所有要经过的点到根所经过的边权和减去最大的边权。

代码

vector好慢啊

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=;
int d[maxn], fa[maxn];
struct Edge{int u,v,dis;};
vector<int> G[maxn];vector<Edge> edges;
int n, ans;
int val[maxn], vis[maxn];
void Addedge(int u,int v,int dis){
edges.push_back((Edge){u,v,dis});edges.push_back((Edge){v,u,dis});
int m=edges.size()-;G[u].push_back(m-);G[v].push_back(m);
}
int dfs(int x,int f,int depth){
fa[x]=f; d[x]=depth;
for(int i=;i<G[x].size();i++){
Edge v=edges[G[x][i]];
if(v.v==f) continue;
dfs(v.v,x,depth+v.dis);
if(vis[v.v]) vis[x]=,ans+=edges[G[x][i]].dis*;
}
}
int main(){
int n,k,a,b,c;
scanf("%d%d",&n,&k);
for(int i=;i<n-;i++){
scanf("%d%d%d",&a,&b,&c);
Addedge(a,b,c);
}
int m; scanf("%d",&m);
for(int i=;i<m;i++){
scanf("%d",&val[i]); vis[val[i]]=;
}
dfs(k,,);
int maxnum=;
for(int i=;i<=n;i++){
if(vis[i]) maxnum=max(maxnum,d[i]);
}
printf("%d",ans- maxnum);
return ;
}
/*
4 2
1 2 1
4 2 2
2 3 3
1
1
*/

【POJ】1935 Journey(树形dp)的更多相关文章

  1. &lbrack;POJ 1155&rsqb; TELE &lpar;树形dp&rpar;

    题目链接:http://poj.org/problem?id=1155 题目大意:电视台要广播电视节目,要经过中转机构,到观众.从电视台到中转商到观众是一个树形结构,经过一条边需要支付成本.现在给你每 ...

  2. Apple Tree POJ - 2486 (树形dp)

    题目链接: D - 树形dp  POJ - 2486 题目大意:一颗树,n个点(1-n),n-1条边,每个点上有一个权值,求从1出发,走V步,最多能遍历到的权值 学习网址:https://blog.c ...

  3. Anniversary party POJ - 2342 (树形DP)

    题目链接:  POJ - 2342 题目大意:给你n个人,然后每个人的重要性,以及两个人之间的附属关系,当上属选择的时候,他的下属不能选择,只要是两个人不互相冲突即可.然后问你以最高领导为起始点的关系 ...

  4. POJ 3107&period;Godfather 树形dp

    Godfather Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 7536   Accepted: 2659 Descrip ...

  5. POJ 3342 (树形DP)

    题意 :给出一些上下级关系,要求i和i的直接上级不能同时出现,现在选出一些人构成一个集合,问你这个集合里面的最大人数是都少,同时给出这个最大的人数的集合是否唯一. 思路:树形DP,dp[i][0],表 ...

  6. POJ 2342 (树形DP)

    Anniversary party Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 3863   Accepted: 2172 ...

  7. POJ Anniversary party 树形DP

    /* 树形dp: 给一颗树,要求一组节点,节点之间没有父子关系,并且使得所有的节点的权值和最大 对于每一个节点,我们有两种状态 dp[i][0]表示不选择节点i,以节点i为根的子树所能形成的节点集所能 ...

  8. POJ 1947Rebuilding Roads&lpar;树形DP &plus; 01背包&rpar;

    题目链接 题意:给出一个树形结构,求P个节点的子树最少要去掉几条边 分析:DP[root][j] 表示 以第 root 个为根节点, 包含j 个节点需要去掉几条边.那么对于 root 这个根节点来说, ...

  9. POJ 1947 (树形DP&plus;背包&rpar;

    题目链接: http://poj.org/problem?id=1947 题目大意:树中各点都由一条边连接.问要弄出个含有m个点的(子)树,至少需要截去多少条边. 解题思路: 设dp[i][j]为i总 ...

  10. Tree Cutting POJ - 2378 (树形DP)

    题目链接:POJ - 2378 题目大意:给你n个点,然后问你这n个点中 ,去除哪些点能够使得剩下的图中最大的连通块中点的个数不超过n/2. 具体思路:第一遍dfs记录每一个点代表的子树大小,第二遍d ...

随机推荐

  1. JavaScript replace&lpar;&rpar; 方法

    参考:http://www.w3school.com.cn/jsref/jsref_replace.asp 需要有一点注意的是:可以是函数的形式做为返回值,如下: "test{0}&quot ...

  2. Laravel 5&period;1 文档攻略 —— Eloquent&colon;模型对象序列化

    在写api的时候,数据一般是以json格式进行传输的,没有对象可以直接使用.这个时候,对数据的序列化转换就很重要,Eloquent提供了很方便的方法和约定,不仅可以转换,还可以控制里面的键值. 基本用 ...

  3. JBoss和Tomcat版本、及Servlet、JSP规范版本对应一览 【转】

    原文地址:http://blog.csdn.net/hills/article/details/40896357 JBoss和Tomcat版本.及Servlet.JSP规范版本对应一览 JBossAS ...

  4. IOS&lowbar;改变UITextField placeHolder颜色、字体

    http://blog.sina.com.cn/s/blog_671d2e4f0101d90v.html

  5. jquery&period;validate的使用

    在页面上面引用 <script type="text/JavaScript" src="js/jQuery.js"></script> ...

  6. python变量类型&amp&semi;字符串的内建函数使用

    python常用数据类型: 数字(整数int,浮点数float) 字符串 元组 列表 字典 一.格式化输出 1.1第一种格式化输出 %d整数  %f浮点数(用.*表示精确到多少位小数) %s字符串 % ...

  7. CentOS 6&period;5 安装mysql 过程记录

    下载的时候一定选对应的版本, el6 还是el7 或者其他版本,不然会出现意向不到的惊喜 比如:我刚开始的时候下载的 el7 版本的 mysql , 然后安装的时候 就会出现: libc.so.(GL ...

  8. what&&num;39&semi;s the python之基本运算符及字符串、列表、元祖、集合、字典的内置方法

    计算机可以进行的运算有很多种,运算按种类可分为算数运算.比较运算.逻辑运算.赋值运算.成员运算.身份运算.字符串和列表的算数运算只能用+和*,字典没有顺序,所以不能进行算数运算和比较运算.比较运算中= ...

  9. Vue&period;js路由

    有时候,我们在用vue的时候会有这样的需求,比如一个管理系统,点了左边的菜单栏,右边跳转到一个新的页面中,而且刷新的时候还会停留在原来打开的页面. 又或者,一个页面中几个不同的画面来回点击切换,这两种 ...

  10. Lua------------------改善Unity编辑器对Lua文件的支持

    原创 2017年03月10日 18:44:22 标签: Unity / lua / 编辑器 952 当前版本的Unity(截至Unity5.5.x)中TextAsset类不支持后缀为lua的文件,将l ...