国产探花免费观看_亚洲丰满少妇自慰呻吟_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);

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板： 应用必备| 建瓯市| 成都市| 哈巴河县| 宁陵县| 静安区| 侯马市| 延寿县| 乐业县| 石河子市| 北票市| 洪雅县| 贵定县| 吉木乃县| 镇康县| 晋宁县| 崇阳县| 潮州市| 肃北| 都匀市| 娱乐| 郸城县| 台前县| 万载县| 贡嘎县| 南开区| 大冶市| 永兴县| 遵义县| 德钦县| 黔江区| 普格县| 老河口市| 定陶县| 镇江市| 公安县| 搜索| 泗洪县| 宜城市| 湘潭市| 广饶县|