首页 > 代码库 > bzoj2286 [Sdoi2011]消耗战
bzoj2286 [Sdoi2011]消耗战
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2286
【题解】这bzoj题目少了一个右括号……
这题朴素dp是O(nq)的,f[x]表示x及其子树有补给站的断开的min,直接转移。
发现这样无用的点很多,考虑建虚树,虚树上的点只有最多2m个。那么复杂度就正确啦
参考:http://www.cnblogs.com/zzqsblog/p/5560645.html
(没错图就是搬来的)
上面的图为关键点,下面的图为虚树上的点。
可以看出来是一坨LCA。那怎么维护呢
栈里维护根到这个点的序列
按照DFS序顺序维护,每到一个点,求和栈顶的LCA,找到什么时候换了一条路线(从根->原来的u,变成根->现在的u)
把这以后的全部pop,连边,再压入新的即可。
然后进行一遍正常的dp。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; # define RG register # define ST static int n; struct Graph { int n, head[M], nxt[M], to[M], w[M], tot; inline void set(int _n) { n = _n; tot = 0; for (int i=1; i<=n; ++i) head[i] = 0; } inline void add(int u, int v, int _w) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; w[tot] = _w; } inline void adde(int u, int v, int _w) { add(u, v, _w); add(v, u, _w); } }G, T; int dep[M], fa[M][20]; int dis[M][20], dfn[M], DFN=0; inline void dfs(int x, int father=0) { dfn[x] = ++DFN; for (int i=1; i<=19; ++i) fa[x][i] = fa[fa[x][i-1]][i-1]; for (int i=1; i<=19; ++i) dis[x][i] = min(dis[fa[x][i-1]][i-1], dis[x][i-1]); for (int i=G.head[x]; i; i=G.nxt[i]) if(G.to[i] != father) { dep[G.to[i]] = dep[x] + 1; fa[G.to[i]][0] = x; dis[G.to[i]][0] = G.w[i]; dfs(G.to[i], x); } } inline int lca(int u, int v) { if(dep[u] < dep[v]) swap(u, v); for (int i=19; ~i; --i) if((dep[u] - dep[v])&(1<<i)) u = fa[u][i]; if(u == v) return u; for (int i=19; ~i; --i) if(fa[u][i] != fa[v][i]) { u = fa[u][i]; v = fa[v][i]; } return fa[u][0]; } inline int getdis(int u, int v) { int d = 1e9; if(dep[u] < dep[v]) swap(u, v); for (int i=19; ~i; --i) if((dep[u] - dep[v])&(1<<i)) { d = min(d, dis[u][i]); u = fa[u][i]; } if(u == v) return d; for (int i=19; ~i; --i) if(fa[u][i] != fa[v][i]) { d = min(d, dis[u][i]); d = min(d, dis[v][i]); u = fa[u][i]; v = fa[v][i]; } d = min(d, dis[u][0]), d = min(d, dis[v][0]); return d; } inline void Tadd(int u, int v) { T.adde(u, v, getdis(u, v)); } ll f[M]; bool g[M]; inline void dp(int x, int fa=0) { f[x] = 0; for (int i=T.head[x]; i; i=T.nxt[i]) { if(T.to[i] == fa) continue; dp(T.to[i], x); if(g[T.to[i]]) f[x] += T.w[i]; else f[x] += min((ll)T.w[i], f[T.to[i]]); } T.head[x] = 0; } int m, a[M], st[M], stn; inline bool cmp_dfn(int x, int y) { return dfn[x] < dfn[y]; } inline void sol() { scanf("%d", &m); for (int i=1; i<=m; ++i) scanf("%d", &a[i]); sort(a+1, a+m+1, cmp_dfn); for (int i=1; i<=m; ++i) g[a[i]] = 1; T.tot = 0; stn = 0; st[++stn] = 1; for (int i=1; i<=m; ++i) { int LCA = lca(a[i], st[stn]); while(stn && dep[st[stn]] > dep[LCA]) { if(stn > 1) { if(dep[st[stn-1]] > dep[LCA]) Tadd(st[stn], st[stn-1]); else Tadd(st[stn], LCA); } --stn; } if(st[stn] != LCA) st[++stn] = LCA; st[++stn] = a[i]; } while(stn>1) { Tadd(st[stn], st[stn-1]); --stn; } dp(1); printf("%lld\n", f[1]); for (int i=1; i<=m; ++i) g[a[i]] = 0; } int main() { cin >> n; G.set(n); for (int i=1, u, v, _w; i<n; ++i) { scanf("%d%d%d", &u, &v, &_w); G.adde(u, v, _w); } dep[1] = 1; dfs(1); int Q; cin >> Q; while(Q--) sol(); return 0; }
bzoj2286 [Sdoi2011]消耗战
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。