主要思路
这个题很神仙啊。首先考虑这个函数是一个单峰函数,且最后多个点所构成的代价函数一定形如 \(y = ax^{\frac{3}{2}} + b\),显然这个函数也是单峰的。所以,当树的形态为一条链时,我们可以尝试二分。如果进化成一颗树,我们可以考虑进行点分治,考虑当前与根连接的子树里,只有一个以下的子树是更优的。
Continue reading →这个题很神仙啊。首先考虑这个函数是一个单峰函数,且最后多个点所构成的代价函数一定形如 \(y = ax^{\frac{3}{2}} + b\),显然这个函数也是单峰的。所以,当树的形态为一条链时,我们可以尝试二分。如果进化成一颗树,我们可以考虑进行点分治,考虑当前与根连接的子树里,只有一个以下的子树是更优的。
Continue reading →这个题还蛮神仙的。主要的思路就是算三元组 \( (p_1, p_2, p_3) \),满足 \( G(S(p_1, p_2)) = G(S(p_2, p_3)) = G(S(p_1, p_3)) = x \)。我们先考虑 \(G(S(p_1, p_2)) = x\) 的 \((p_1, p_2)\)。假设我们能把这些路径全部求出来,并把这个仅包含有向边 \( S(p_1, p_2) \) 的有向图的入度、出度算出来。如果能算出这种东西的话,发现直接乘法原理可以算出非法的三元组(合法的三元组是没法搞的,因为你还得算 \( (p_1, p_3) \) 的东西才能搞)。如果规定时间内能搞定这个入度出度之后,我们直接 \(\Theta(n)\) 算掉乘法原理那个。搞入度出度可以直接上点分治。
先可以想到把所有的包含的区间给去掉,然后来关注如何进行 DP。我们可以考虑设置 \(dp[i][j]\) 为前 \(i\) 个区间里删掉了 \(j\) 个区间的最优答案。正常我们做「选择 \(j\) 个区间」的问题会比较简单,然而 \(k \leq 200\) 就很麻烦。
这道题是一道很考察思维的题目,我在这里介绍 DP 的做法。
我们考虑 DP。大概的方程可以写成:
\[ dp[i] = max\{ dp[j], j \in S_i \} + 1 \]
其中,\(dp[i]\)代表\([1, i]\)之间最多的斑点奶牛数量,然后\(S_i\)就是我们可以转移来的区间。我们可以提前处理好每一个点对应的\(lft_{S_i}, rig_{S_i}\),也就是每一个点集合的左右端点。这个区间满足一个根本的条件:这个区间是点\(i\)左边最近的、不包含\(i\)的集合。我们肯定可以从这一段区间搞出最大的答案。预处理的时候先默认\(rgt[i] = i – 1\),最后做个小 DP 更新数据即可。
这道题应该算是点分治的一道经典题目。点分治的精髓就在于找到重心、对子树进行计算并且合并答案,之后删除中心变成子树内的小问题,分治思想非常的巧妙。
我们首先写好找根函数:
// root finding functions; void dfs1(int u, int fa, int siz) { son[u] = 1; int res = 0; for (int i = head[u]; i != -1; i = edges[i].nxt) { if (edges[i].to == fa || done[edges[i].to]) continue; dfs1(edges[i].to, u, siz); son[u] += son[edges[i].to]; res = max(res, son[edges[i].to] - 1); } res = max(res, siz - son[u]); if (res < rootKey) root = u, rootKey = res; } void findRoot(int src, int siz) { root = src, rootKey = siz; dfs1(src, 0, siz); }
遍历子树:我们设定一个\(dist[]\)数组,算出距离的答案,并且无视曾经被当作根的节点,并向cnt[from[u]]
进行自增操作,维护子树的大小,并把本身编号加入vec
供之后进行排序用途。
// the calc one; void dfs(int u, int fa) { vec.push_back(u); for (int i = head[u]; i != -1; i = edges[i].nxt) if (edges[i].to != fa && !done[edges[i].to]) { cnt[from[u]]++; dist[edges[i].to] = dist[u] + edges[i].weight; from[edges[i].to] = from[u]; dfs(edges[i].to, u); } }
点分治:我们在计算完子树答案之后,合并的方法是主要的问题。我们可以考虑将vec
进行排序,然后通过递增的性质设置首尾指针,并且去除掉当前子树内的错误答案(因为子树内部的路径不经过根,所以要去掉,之后的分治子问题中会处理这些内部路径)。
void pdq(int curt, int siz) { memset(son, 0, sizeof(son)); memset(cnt, 0, sizeof(cnt)); findRoot(curt, siz); dist[root] = 0, done[root] = true; vec.clear(), vec.push_back(root), from[root] = root; cnt[root]++; for (int i = head[root]; i != -1; i = edges[i].nxt) if (!done[edges[i].to]) { from[edges[i].to] = edges[i].to, cnt[edges[i].to]++; dist[edges[i].to] = edges[i].weight; dfs(edges[i].to, root); } sort(vec.begin(), vec.end(), compare); cnt[from[vec[0]]]--; int l = 0, r = vec.size() - 1; while (l < r) { while (dist[vec[l]] + dist[vec[r]] > k) cnt[from[vec[r--]]]--; answer += r - l - cnt[from[vec[l]]]; cnt[from[vec[++l]]]--; } int pos = root; for (int i = head[pos]; i != -1; i = edges[i].nxt) if (!done[edges[i].to]) pdq(edges[i].to, son[edges[i].to]); }
嗯,写完了。具体代码如下:
// POJ1741.cpp #include <cstdio> #include <vector> #include <algorithm> #include <iostream> #include <cstring> using namespace std; const int MAX_N = 10100, INF = 0x3f3f3f3f; int head[MAX_N], current, k, n, tmpx, tmpy, tmpz, root, rootKey, son[MAX_N]; int from[MAX_N], dist[MAX_N], cnt[MAX_N]; bool done[MAX_N]; long long answer = 0; vector<int> vec; struct edge { int to, nxt, weight; } edges[MAX_N << 1]; bool compare(int a, int b) { return dist[a] < dist[b]; } void addpath(int src, int dst, int weight) { edges[current].to = dst, edges[current].nxt = head[src]; edges[current].weight = weight, head[src] = current++; } // root finding functions; void dfs1(int u, int fa, int siz) { son[u] = 1; int res = 0; for (int i = head[u]; i != -1; i = edges[i].nxt) { if (edges[i].to == fa || done[edges[i].to]) continue; dfs1(edges[i].to, u, siz); son[u] += son[edges[i].to]; res = max(res, son[edges[i].to] - 1); } res = max(res, siz - son[u]); if (res < rootKey) root = u, rootKey = res; } void findRoot(int src, int siz) { root = src, rootKey = siz; dfs1(src, 0, siz); } // the calc one; void dfs(int u, int fa) { vec.push_back(u); for (int i = head[u]; i != -1; i = edges[i].nxt) if (edges[i].to != fa && !done[edges[i].to]) { cnt[from[u]]++; dist[edges[i].to] = dist[u] + edges[i].weight; from[edges[i].to] = from[u]; dfs(edges[i].to, u); } } void pdq(int curt, int siz) { memset(son, 0, sizeof(son)); memset(cnt, 0, sizeof(cnt)); findRoot(curt, siz); dist[root] = 0, done[root] = true; vec.clear(), vec.push_back(root), from[root] = root; cnt[root]++; for (int i = head[root]; i != -1; i = edges[i].nxt) if (!done[edges[i].to]) { from[edges[i].to] = edges[i].to, cnt[edges[i].to]++; dist[edges[i].to] = edges[i].weight; dfs(edges[i].to, root); } sort(vec.begin(), vec.end(), compare); cnt[from[vec[0]]]--; int l = 0, r = vec.size() - 1; while (l < r) { while (dist[vec[l]] + dist[vec[r]] > k) cnt[from[vec[r--]]]--; answer += r - l - cnt[from[vec[l]]]; cnt[from[vec[++l]]]--; } int pos = root; for (int i = head[pos]; i != -1; i = edges[i].nxt) if (!done[edges[i].to]) pdq(edges[i].to, son[edges[i].to]); } int main() { while (scanf("%d%d", &n, &k) && n != 0) { answer = 0; memset(head, -1, sizeof(head)), current = 0; for (int i = 1; i <= n - 1; i++) scanf("%d%d%d", &tmpx, &tmpy, &tmpz), addpath(tmpx, tmpy, tmpz), addpath(tmpy, tmpx, tmpz); memset(done, false, sizeof(done)); pdq(1, n); printf("%lld\n", answer); } return 0; }
这道题我们直接进行点分治即可。我们需要实现一下的几个操作:
我们一段一段来讲。
void predfs(int u, int fa) { siz[u] = 1, son[u] = 0; for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to, w = edges[i].weight; if (to == fa || vis[to]) continue; predfs(to, u); siz[u] += siz[to], son[u] = max(siz[to], son[u]); } son[u] = max(son[u], capacity - siz[u]); if (son[u] < son[root]) root = u; }
这一段是找重心的代码,很简单我就不解释了。
void getMeta(int u, int fa, int cnt, int dist) { if (dist > k) return; ans = min(ans, sides[k - dist] + cnt); for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (to == fa || vis[to]) continue; getMeta(to, u, cnt + 1, dist + edges[i].weight); } }
这段比较重要。点分治出来之后就进行子树上的答案统计,答案的计算为\(ans=min\{sides[k – dist] + cnt\}\),其中 sides 数组代表长度为 dist 的最小段数。统计的时候不用担心边重复的问题,因为我们之后 update 操作之后才会让 sides 数组生效。
void update(int u, int fa, int cnt, int dist) { if (dist > k) return; sides[dist] = min(sides[dist], cnt); for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (to == fa || vis[to]) continue; update(to, u, cnt + 1, dist + edges[i].weight); } }
用 DFS 进行更新。
void clear(int u, int fa, int dis) { if (dis >= k) return; sides[dis] = 1e9; for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (vis[to] || fa == to) continue; clear(to, u, dis + edges[i].weight); } }
设置为极大值来覆盖子树恢复答案。
void divide(int u, int sz) { vis[u] = true, sides[0] = 0; for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (vis[to]) continue; getMeta(to, u, 1, edges[i].weight); update(to, u, 1, edges[i].weight); } clear(u, 0, 0); for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (vis[to]) continue; son[0] = capacity = (siz[to] > siz[u]) ? (sz - siz[u]) : (siz[to]); root = 0; predfs(to, 0); divide(root, capacity); } }
点分治是在重心上运行的。在重心上更新子树的信息,然后进行换根保证正确性。
// P4149.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 200200; struct edge { int to, nxt, weight; } edges[MAX_N << 1]; int head[MAX_N], n, k, current, tmpx, tmpy, tmpz, siz[MAX_N], capacity; int ans = 1e9, sides[1002000], son[MAX_N], root; bool vis[MAX_N]; inline int read() { int re = 0, flag = 1; char ch = getchar(); while (ch > '9' || ch < '0') { if (ch == '-') flag = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') re = (re << 1) + (re << 3) + ch - '0', ch = getchar(); return re * flag; } void addpath(int src, int dst, int weight) { edges[current].to = dst, edges[current].nxt = head[src]; edges[current].weight = weight, head[src] = current++; } void predfs(int u, int fa) { siz[u] = 1, son[u] = 0; for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to, w = edges[i].weight; if (to == fa || vis[to]) continue; predfs(to, u); siz[u] += siz[to], son[u] = max(siz[to], son[u]); } son[u] = max(son[u], capacity - siz[u]); if (son[u] < son[root]) root = u; } void getMeta(int u, int fa, int cnt, int dist) { if (dist > k) return; ans = min(ans, sides[k - dist] + cnt); for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (to == fa || vis[to]) continue; getMeta(to, u, cnt + 1, dist + edges[i].weight); } } void update(int u, int fa, int cnt, int dist) { if (dist > k) return; sides[dist] = min(sides[dist], cnt); for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (to == fa || vis[to]) continue; update(to, u, cnt + 1, dist + edges[i].weight); } } void clear(int u, int fa, int dis) { if (dis >= k) return; sides[dis] = 1e9; for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (vis[to] || fa == to) continue; clear(to, u, dis + edges[i].weight); } } void divide(int u, int sz) { vis[u] = true, sides[0] = 0; for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (vis[to]) continue; getMeta(to, u, 1, edges[i].weight); update(to, u, 1, edges[i].weight); } clear(u, 0, 0); for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (vis[to]) continue; son[0] = capacity = (siz[to] > siz[u]) ? (sz - siz[u]) : (siz[to]); root = 0; predfs(to, 0); divide(root, capacity); } } int main() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &k); for (int i = 0; i < n - 1; i++) { scanf("%d%d%d", &tmpx, &tmpy, &tmpz); addpath(tmpx + 1, tmpy + 1, tmpz), addpath(tmpy + 1, tmpx + 1, tmpz); } capacity = n; son[0] = n, root = 0; for (int i = 0; i <= k; i++) sides[i] = 1e9; predfs(1, 0); divide(root, n); if (ans != 1e9) printf("%d", ans); else printf("-1"); return 0; }