[BZOJ3365][Usaco2004 Feb]Distance Statistics 路程统计（点分治）

2019-11-08 19:49:01

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

裸的点分治每一次排序之后扫一遍统计就行了

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 40005int n,m,k,x,y,z,sum,root,ans;int tot,point[N],nxt[N*2],v[N*2],c[N*2];int big[N],size[N],d[N],deep[N];bool vis[N];void add(int x,int y,int z){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z;}void getroot(int x,int fa){ size[x]=1;big[x]=0; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!vis[v[i]]) { getroot(v[i],x); size[x]+=size[v[i]]; big[x]=max(big[x],size[v[i]]); } big[x]=max(big[x],sum-size[x]); if (big[x]<big[root]) root=x;}void getdeep(int x,int fa){ deep[++deep[0]]=d[x]; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!vis[v[i]]) { d[v[i]]=d[x]+c[i]; getdeep(v[i],x); }}int calc(int x,int now){ d[x]=now;deep[0]=0; getdeep(x,0); sort(deep+1,deep+deep[0]+1); int t=0; for (int l=1,r=deep[0];l<r;) { if (deep[l]+deep[r]<=k) t+=r-l,++l; else --r; } return t;}void dfs(int x){ ans+=calc(x,0); vis[x]=1; for (int i=point[x];i;i=nxt[i]) if (!vis[v[i]]) { ans-=calc(v[i],c[i]); sum=size[v[i]];root=0; getroot(v[i],0); dfs(root); }}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=m;++i) { scanf("%d%d%d %c",&x,&y,&z,&d); add(x,y,z),add(y,x,z); } scanf("%d",&k); sum=n;root=0;big[0]=N; getroot(1,0); dfs(root); PRintf("%d/n",ans);}

上一篇：线段树标记永久化个人理解 & BZOJ 1513 [POI2006]Tet-Tetris 3D

下一篇：蓝桥杯ALGO-3 K好数