首页 > 代码库 > POJ 1741

POJ 1741

2024-08-25 15:44:42   220人阅读

题意就是求树上距离小于等于K的点对有多少个

n2的算法肯定不行，因为1W个点

这就需要分治。可以看09年漆子超的论文

本题用到的是关于点的分治。

一个重要的问题是，为了防止退化，所以每次都要找到树的重心然后分治下去，所谓重心，就是删掉此结点后，剩下的结点最多的树结点个数最小。

每次分治，我们首先算出重心，为了计算重心，需要进行两次dfs，第一次把以每个结点为根的子树大小求出来，第二次是从这些结点中找重心

找到重心后，需要统计所有结点到重心的距离，看其中有多少对小于等于K，这里采用的方法就是把所有的距离存在一个数组里，进行快速排序，这是nlogn的，然后用一个经典的相向搜索O(n)时间内解决。但是这些求出来满足小于等于K的里面只有那些路径经过重心的点对才是有效的，也就是说在同一颗子树上的肯定不算数的，所以对每颗子树，把子树内部的满足条件的点对减去。

最后的复杂度是n logn logn    其中每次快排是nlogn 而递归的深度为logn。

  1 #include <iostream>    2 #include <algorithm>    3 #include <cstring>    4 #include <string>    5 #include <cstdio>    6 #include <cmath>    7 #include <queue>    8 #include <map>    9 #include <set>   10 #define eps 1e-5   11 #define MAXN 11111   12 #define MAXM 55555   13 #define INF 1000000000   14 using namespace std;   15 struct EDGE   16 {   17     int v, next, w;   18 }edge[MAXM];   19 int head[MAXN], e;   20 int n, k, vis[MAXN], ans, root, num;   21 void init()   22 {   23     memset(vis, 0, sizeof(vis));   24     memset(head, -1, sizeof(head));   25     e = ans = 0;   26 }   27 void add(int u, int v, int w)   28 {   29     edge[e].v = v;   30     edge[e].w = w;   31     edge[e].next = head[u];   32     head[u] = e++;   33 }   34 int mx[MAXN], size[MAXN], mi, dis[MAXN];   35 void dfssize(int u, int fa) //处理子树的大小   36 {   37     size[u] = 1;   38     mx[u] = 0;   39     for(int i = head[u]; i != -1; i = edge[i].next)   40     {   41         int v = edge[i].v;   42         if(v != fa && !vis[v])   43         {   44             dfssize(v, u);   45             size[u] += size[v];   46             if(size[v] > mx[u]) mx[u] = size[v];   47         }   48     }   49 }   50 void dfsroot(int r, int u, int fa) //求重心   51 {   52     if(size[r] - size[u] > mx[u]) mx[u] = size[r] - size[u];   53     if(mx[u] < mi) mi = mx[u], root = u;   54     for(int i = head[u]; i != -1; i = edge[i].next)   55     {   56         int v = edge[i].v;   57         if(v != fa && !vis[v]) dfsroot(r, v, u);   58     }   59 }   60 void dfsdis(int u, int d, int fa) //求距离   61 {   62     dis[num++] = d;   63     for(int i = head[u]; i != -1; i = edge[i].next)   64     {   65         int v = edge[i].v;   66         if(v != fa && !vis[v]) dfsdis(v, d + edge[i].w, u);   67     }   68 }   69 int calc(int u, int d)   70 {   71     int ret = 0;   72     num = 0;   73     dfsdis(u, d, 0);   74     sort(dis, dis + num);   75     int i = 0, j = num - 1;   76     while(i < j) //经典   77     {   78         while(dis[i] + dis[j] > k && i < j) j--;   79         ret += j - i;   80         i++;   81     }   82     return ret;   83 }   84 void dfs(int u)   85 {   86     mi = n;   87     dfssize(u, 0);   88     dfsroot(u, u, 0);   89     ans += calc(root, 0);   90     vis[root] = 1;   91     for(int i = head[root]; i != -1; i = edge[i].next)   92     {   93         int v = edge[i].v;   94         if(!vis[v])   95         {   96             ans -= calc(v, edge[i].w);   97             dfs(v);   98         }   99     }  100 }  101 int main()  102 {  103     while(scanf("%d%d", &n, &k) != EOF)  104     {  105         if(!n && !k) break;  106         init();  107         int u, v, w;  108         for(int i = 0; i < n - 1; i++)  109         {  110             scanf("%d%d%d", &u, &v, &w);  111             add(u, v, w);  112             add(v, u, w);  113         }  114         dfs(1);  115         printf("%d\n", ans);  116     }  117     return 0;  118 }

另附网址：09年漆子超论文　　提取密码：95tu

POJ 1741


联系
我们