hdu - 3660 - Alice and Bob's Trip

发布时间:2017-2-27 14:37:59 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu - 3660 - Alice and Bob's Trip",主要涉及到hdu - 3660 - Alice and Bob's Trip方面的内容,对于hdu - 3660 - Alice and Bob's Trip感兴趣的同学可以参考一下。

题意:一棵有n个结点的树,编号从0(根结点)开始,Alice和Bob一起从0走到叶子结点,Alice走最短路,Bob走最长路,Bob先选择下一个结点,然后两个一起走到那个结点,接着Alice选择下一个结点……,总长度要在[L, R]内,问这种走法的最长路的长度(1 <= n <= 500000, 0 <= L, R <= 1000000000, 1 <= 相邻结点间距离 <= 1000)。 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3660 ——>>怒刷树状dp。。。 设da[i]为Alice从结点i出发走到叶子的最短距离,则 状态转移方程为:da[x] = min(da[x], db[v[e]] + w[e]); 设db[i]为Bob从结点i出发走到叶子的最长距离,则 状态转移方程为:db[x] = max(db[x], da[v[e]] + w[e]); 加上IO优化,以C++提交~ #include <cstdio> #include <cstring> #include <algorithm> #include <cctype> using namespace std; const int maxn = 500000 + 10; const int INF = 0x3f3f3f3f; int n, L, R, head[maxn], nxt[maxn], u[maxn], v[maxn], w[maxn], ecnt, da[maxn], db[maxn]; void init(){ ecnt = 0; memset(head, -1, sizeof(head)); } void addEdge(int uu, int vv, int ww){ u[ecnt] = uu; v[ecnt] = vv; w[ecnt] = ww; nxt[ecnt] = head[uu]; head[uu] = ecnt; ecnt++; } int nextInt(){ char c = getchar(); while(!isdigit(c)) c = getchar(); int ret = 0; while(isdigit(c)){ ret = ret * 10 + c - '0'; c = getchar(); } return ret; } void read(){ int uu, vv, ww, i; for(i = 0; i < n-1; i++){ uu = nextInt(); vv = nextInt(); ww = nextInt(); addEdge(uu, vv, ww); } } void dp(int x, int cur){ da[x] = head[x] == -1 ? 0 : INF; db[x] = 0; for(int e = head[x]; e != -1; e = nxt[e]){ int len = cur + w[e]; if(len <= R) dp(v[e], len); if(len + db[v[e]] >= L && len + db[v[e]] <= R) da[x] = min(da[x], db[v[e]] + w[e]); if(len + da[v[e]] >= L && len + da[v[e]] <= R) db[x] = max(db[x], da[v[e]] + w[e]); } } void solve(){ dp(0, 0); if(db[0]) printf("%d\n", db[0]); else puts("Oh, my god!"); } int main() { while(scanf("%d%d%d", &n, &L, &R) == 3){ init(); read(); solve(); } return 0; }

上一篇:poj 2513 Colored Sticks (字典树+欧拉回路判定)
下一篇:poj1220 (高精度任意进制转换)

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。