漂流:给定一颗树及各边长度,请快速查询是否有距离为k的顶点对。
4.6划分、解决、合并:分治法
树上的分治法
与POJ1741类似
只需将“不超过k”改为“不超过k减去小于k”,就可以得到“等于k”的数量了。
int count_pairs(vector<int> &ds) { int res = 0; sort(ds.begin(), ds.end()); int j = ds.size(); for (int i = 0; i < ds.size(); i++) { while (j > 0 && ds[i] + ds[j - 1] > k) j--; res += j - (j > i ? 1 : 0);//除去和本身组成的点对 } j = ds.size(); for (int i = 0; i < ds.size(); i++) { while (j > 0 && ds[i] + ds[j - 1] >= k) j--; res -= j - (j > i ? 1 : 0);//除去和本身组成的点对 } return res; }
书上的模板不太给力,能跑对CTU Open 2004,但在POJ上一直TLE。
后来给两个vector加个static就过了,依然这么洒脱
#include <iostream> #include <vector> #include <cstdio> #include <utility> #include <algorithm> #include <cstring> using namespace std; const int MAX_N = 10000 + 10; #define INF 0x3f3f3f3f struct edge { int to, length; }; vector<edge> G[MAX_N]; int n, k; bool centroid[MAX_N];//顶点是否已作为重心删除的标记 int subtree_size[MAX_N];//以该顶点为根的子树的大小(查找重心时用) int ans;//答案 //计算子树大小(subtree_size)的递归函数 int compute_subtree_size(int v, int p) { int c = 1; for (int i = 0; i < G[v].size(); i++) { int w = G[v][i].to; if (w == p || centroid[w]) continue; c += compute_subtree_size(G[v][i].to, v); } subtree_size[v] = c; return c; } //查找重心的递归函数,t是整个连通分量的大小 //在以v为根的子树中寻找一个顶点,使得删除该顶点后最大子树的顶点数最小 //返回值为pair(最大子树的顶点数,顶点编号) pair<int, int> search_centroid(int v, int p, int t) { pair<int, int> res = make_pair(INF, -1); //s是以v为根的子树的大小 //m是删除v后最大子树的顶点数 int s = 1, m = 0; for (int i = 0; i < G[v].size(); i++) { int w = G[v][i].to; if (w == p || centroid[w]) continue; res = min(res, search_centroid(w, v, t)); m = max(m, subtree_size[w]); s += subtree_size[w]; } m = max(m, t - s); res = min(res, make_pair(m, v)); return res; } //计算子树中的所有顶点到重心的距离 void enumerate_paths(int v, int p, int d, vector<int> &ds) { ds.push_back(d); for (int i = 0; i < G[v].size(); i++) { int w = G[v][i].to; if (w == p || centroid[w]) continue; enumerate_paths(w, v, d + G[v][i].length, ds); } } //统计和不超过K的顶点对的个数 int count_pairs(vector<int> &ds) { int res = 0; sort(ds.begin(), ds.end()); int j = ds.size(); for (int i = 0; i < ds.size(); i++) { while (j > 0 && ds[i] + ds[j - 1] > k) j--; res += j - (j > i ? 1 : 0);//除去和本身组成的点对 } j = ds.size(); for (int i = 0; i < ds.size(); i++) { while (j > 0 && ds[i] + ds[j - 1] >= k) j--; res -= j - (j > i ? 1 : 0);//除去和本身组成的点对 } return res; } //对顶点v的子树,查找重心并分割求解的递归函数 void solve_subproblem(int v) { //查找重心s compute_subtree_size(v, -1); int s = search_centroid(v, -1, subtree_size[v]).second; centroid[s] = true; //统计按顶点s分割后子树中的对数 for (int i = 0; i < G[s].size(); i++) { if (centroid[G[s][i].to]) continue; solve_subproblem(G[s][i].to); } //统计经过点s的对数 static vector<int> ds; ds.clear(); ds.push_back(0); for (int i = 0; i < G[s].size(); i++) { if (centroid[G[s][i].to]) continue; static vector<int> tds; tds.clear(); enumerate_paths(G[s][i].to, s, G[s][i].length, tds); ans -= count_pairs(tds); ds.insert(ds.end(), tds.begin(), tds.end()); } ans += count_pairs(ds); centroid[s] = false; } void solve() { ans = 0; solve_subproblem(0); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif while (~scanf("%d", &n) && n) { for (int i = 0; i < n; i++) { G[i].clear(); } for (int u = 0; u < n; u++) { int v, w; while (~scanf("%d", &v) && v) { --v; scanf("%d", &w); G[u].push_back((edge) {v, w}); G[v].push_back((edge) {u, w}); } } while (~scanf("%d", &k) && k) { memset(centroid, 0, sizeof(centroid)); solve(); puts(ans > 0 ? "AYE" : "NAY"); } puts("."); } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }
16530241 | hankcs | 2114 | Accepted | 2556K | 1125MS | G++ | 3721B | 2017-01-31 05:32:30 |