加载中…HDU 3848 CC On The Tree 北邮邀请赛
(2011-07-18 19:16:47)
标签：
hdu3848cconthetree北邮邀请赛it |
分类： 搜索 |
题目描述：
给你n个点的树，每条边有边权，任意选择起点，问经过两个叶子节点的最小花费是多少。
解题报告：
画图不难发现，选择一个非叶子节点作为树根，每个树枝节点到它的叶子的最短的两条路的和就是这个树枝的答案。所有答案的最小值就是解。dfs解之。
代码如下：
int
mina, minb;
pint(int a, int b) :mina(a), minb(b){}
pint(){}
e[cnt].to = to; e[cnt].next = v[from]; e[cnt].val
= val;
v[from]
= cnt++;
if
(b.mina != -1)
{
if (a.mina == -1 || b.mina
<= a.mina)
{
a.minb = a.mina;
a.mina = b.mina;
}else if (a.minb == -1 ||
b.mina < a.minb)
a.minb = b.mina;
}
if
(b.minb != -1)
{
if (a.mina == -1 || b.minb
<= a.mina)
{
a.minb = a.mina;
a.mina = b.minb;
}else if (a.minb == -1 ||
b.minb < a.minb)
a.minb = b.minb;
}
return
a;
if
(d[id] == 1) return pint(0, -1);
pint
jeo = pint(-1, -1);
for(int
i = v[id]; i != -1; i = e[i].next) if (e[i].to != from)
{
pint tmp = dfs(e[i].to,
id);
if (tmp.mina != -1) tmp.mina
+= e[i].val;
if (tmp.minb != -1) tmp.minb
+= e[i].val;
jeo = mmin(jeo, tmp);
}
if
(jeo.mina != -1 && jeo.minb != -1
&& (ans == -1 || jeo.mina +
jeo.minb < ans))
ans = jeo.mina +
jeo.minb;
return
jeo;
while(scanf("%d", &n)
&& n)
{
memset(v, -1, sizeof(v)); cnt
= 0;
memset(d, 0, sizeof(d));
for(int i = 1; i
< n; i++)
{
int a, b, c;scanf("%d%d%d", &a,
&b, &c);
insert(a - 1, b - 1, c); d[a - 1]++; d[b -
1]++;
insert(b - 1, a - 1, c);
}
if (n == 2) {printf("%d\n",
e[0].val);continue;}
else
{
ans = -1;
for(int i = 0; i < n; i++) if
(d[i] >= 2) {dfs(i, -1); break;}
}
printf("%d\n", ans);
}
return
0;
给你n个点的树，每条边有边权，任意选择起点，问经过两个叶子节点的最小花费是多少。
解题报告：
画图不难发现，选择一个非叶子节点作为树根，每个树枝节点到它的叶子的最短的两条路的和就是这个树枝的答案。所有答案的最小值就是解。dfs解之。
代码如下：
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;
int n, cnt, v[10000], ans, d[10000];
struct edge{int to, val, next;}e[20000];
struct pint
{
};
void insert(int from, int to, int val)
{
}
pint mmin(pint a, pint b)
{
}
pint dfs(int id, int from)
{
}
int main()
{
}
喜欢
0
赠金笔