BZOJ1509: [NOI2003]逃学的小孩(树的直径)
2018-07-06 01:20:11来源:博客园 阅读 ()
Submit: 1126 Solved: 567
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
1 2 1
2 3 1
3 4 1
Sample Output
HINT
Source
这题比较naive吧。。
不过我一开始以为C是给出的。
很显然$AB$一定是树的直径。
敲完了才发现C是不固定的以为自己白写了。
但实际上只需要求出直径的端点到每个点的距离,然后在小的里面取最大就好了
#include<cstdio> #include<vector> #include<algorithm> #include<cstring> #include<map> #include<cmath> #include<queue> #define int long long using namespace std; const int INF = 1e9 + 10, MAXN = 1e6 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M; struct Edge { int u, v, w, nxt; }E[MAXN]; int head[MAXN], num = 1; inline void AddEdge(int x, int y, int z) { E[num] = (Edge) {x, y, z, head[x]}; head[x] = num++; } int dis[MAXN], mx, mxdis; void dfs(int x, int fa) { for(int i = head[x]; i != -1; i = E[i].nxt) { if(E[i].v == fa) continue; dis[E[i].v] = dis[x] + E[i].w; dfs(E[i].v, x); if(dis[E[i].v] > mxdis) mxdis = dis[E[i].v], mx = E[i].v; } } int Node1, Node2, dis1[MAXN], dis2[MAXN]; int GetAns() { memset(dis, 0, sizeof(dis)); dfs(Node1, 0); for(int i = 1; i <= N; i++) dis1[i] = dis[i]; memset(dis, 0, sizeof(dis)); dfs(Node2, 0); for(int i = 1; i <= N; i++) dis2[i] = dis[i]; int rt = 0; for(int i = 1; i <= N; i++) rt = max(rt, min(dis1[i], dis2[i])); return rt; } main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif memset(head, -1, sizeof(head)); N = read(); M = read(); for(int i = 1; i <= M; i++) { int x = read(), y = read(), z = read(); AddEdge(x, y, z); AddEdge(y, x, z); } dfs(1, 0); Node1 = mx; memset(dis, 0, sizeof(dis)); mxdis = 0; dfs(mx, 0); Node2 = mx; int ans = dis[mx]; printf("%I64d", ans + GetAns()); }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 定时提醒助手 2018-06-18
- 简单三层复习 2018-06-18
- c++的构造函数 2018-06-17
- devcpp中很简单的排序 2018-06-17
- P2279 [HNOI2003]消防局的设立 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash