软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 编程语言 -> UVA -> 正文阅读
编程语言 最新文章
Java面试题(1)
ReactiveX序列——RxSwift
C++STL之ACM相关知识大全
c++中vector向量几种情况的总结(向量指针,
SSH框架整合demo
JAX
UVA
curl备忘(1)
C#机房重构——万事开头难(二)
OJ刷题

[编程语言]UVA

  2015-04-30 22:58:42

题目传送:UVA - 10308


思路:就是树的遍历,DFS即可,注意输入


AC代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cctype>
#define LL long long
#define INF 0x7fffffff
using namespace std;

struct node {
	int e, w;
	node(int _e, int _w) : e(_e), w(_w) { }
}; 

const int maxn = 10010;
vector<node> G[maxn];

int ans;

int dfs(int u, int fa) {
	int maxx = 0;//maxx表示当前结点到叶子结点的最大权值
	int anss;//anss表示当前结点到叶子结点的权值 
	int len = G[u].size();
	for(int i = 0; i < len; i ++) {
		if(G[u][i].e != fa) {
			anss = dfs(G[u][i].e, u) + G[u][i].w;
			ans = max(ans, anss + maxx);//更新答案 
			maxx = max(anss, maxx);//更新最大权值 
		}
	}
	return maxx;
}

int main() {
	string s;
    while (!cin.eof()) {
    	for(int i = 0; i < maxn; i ++)
			G[i].clear();
        
		getline(cin, s);
        while (s.length() > 0 && !cin.eof())
        {
            stringstream ss;
            ss << s;
            int u, v, w;
            ss >> u >> v >> w;
            G[u].push_back(node(v, w));
            G[v].push_back(node(u, w));

            getline(cin, s);
        }
        ans = 0;
		dfs(1, -1);
		printf("%d\n", ans);
    }
	return 0;
}

上一篇文章      下一篇文章      查看所有文章
2015-04-30 22:55:42  
360图书馆 论文大全 母婴/育儿 软件开发资料 网页快照 文字转语音 购物精选 软件 美食菜谱 新闻中心 电影下载 小游戏 Chinese Culture
生肖星座解梦 人民的名义 人民的名义在线看 三沣玩客 拍拍 视频 开发 Android开发 站长 古典小说 网文精选 搜图网 天下美图
中国文化英文 多播视频 装修知识库
2017-4-24 5:37:17
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --