国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

[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);

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板： 龙口市| 璧山县| 云梦县| 宁城县| 太保市| 丹江口市| 镇平县| 灌阳县| 双流县| 锡林浩特市| 宿松县| 册亨县| 自贡市| 平乡县| 阿瓦提县| 大方县| 嘉兴市| 蓝田县| 石城县| 马鞍山市| 邢台县| 德安县| 岐山县| 旬阳县| 武清区| 松阳县| 衡南县| 文昌市| 韶山市| 全南县| 昆山市| 龙江县| 杭锦旗| 千阳县| 高安市| 山阴县| 新宁县| 边坝县| 达拉特旗| 漳平市| 新兴县|