POJ 1741 Tree【Tree,点分治】

给一棵边带权树，问两点之间的距离小于等于K的点对有多少个。

模板题：就是不断找树的重心，然后分开了，分治，至少分成两半，就是上限为log

然后一起统计就ok了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<algorithm>
 7 #define inf 2000000007
 8 using namespace std;
 9 
10 int n,m;
11 double l,u;
12 double dis[1007];int ins[1007],num[1007];
13 int cnt,head[1007],Next[1000007],rea[1000007];double val[1000007];
14 
15 void add(int u,int v,double fee)
16 {
17     Next[++cnt]=head[u];
18     head[u]=cnt;
19     rea[cnt]=v;
20     val[cnt]=fee;
21 }
22 bool Spfa()
23 {
24     for (int i=1;i<=n+m;i++)
25         dis[i]=inf,ins[i]=0,num[i]=0;
26     queue<int>q;
27     q.push(1);dis[1]=0,ins[1]=num[1]=1;    
28     while(!q.empty())
29     {
30         int u=q.front();q.pop();
31         for (int i=head[u];i!=-1;i=Next[i])
32         {
33             int v=rea[i];double fee=val[u];
34             if (dis[v]>dis[u]+fee)
35             {
36                 dis[v]=dis[u]+fee;
37                 if (!ins[v])
38                 {
39                     ins[v]=1;
40                     q.push(v);
41                     num[v]++;
42                     if (num[v]>sqrt(n+m)) return false;
43                 }
44             }
45         }
46         ins[u]=0;
47     }
48     return true;
49 }
50 int main()
51 {
52     while(~scanf("%d%d%lf%lf",&n,&m,&l,&u))
53     {
54         cnt=0;double x;
55         memset(head,-1,sizeof(head));
56         for(int i=1;i<=n;i++)
57             for(int j=1;j<=m;j++)
58             {
59                 scanf("%lf",&x);
60                 add(j+n,i,log(u)-log(x));
61                 add(i,j+n,log(x)-log(l));
62             }
63         if(Spfa()) puts("YES");
64         else puts("NO");
65     }
66 }