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

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

POJ1741 Tree.

2019-11-11 01:50:04
字體:
來源:轉載
供稿:網友
Give a tree with n vertices,each edge has a length(positive integer less than 1001).Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.Write a PRogram that will count how many pairs which are valid for a given tree. InputThe input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l. The last test case is followed by two zeros. OutputFor each test case output the answer on a single line.Sample Input
5 41 2 31 3 11 4 23 5 10 0Sample Output
8(說起來這應該是人生第一道點分治唄。。。quq蒟蒻的悲哀:)題意:給定一棵N(1<= N <=10000)個結點的帶權樹,定義dist(u,v)為u,v兩點間的最短路徑長度,路徑的長度定義為路徑上所有邊的權和。再給定一個 K  ,如果對于不同的兩個結點a,b,如果滿足dist(a,b) <=K,則稱(a,b)為合法點對。求合法點對個數。題解:也是剛剛搞完點分治唄。。。%XZK難得一次編譯過AC。。。所謂點分治嘞,就是在一個無根樹里選取一個點作為根【重心】然后再遞歸處理每個子樹對于這道題嘛,我們考慮一條路徑只有兩種情況——經過根or不過根【也可以說是:兩點在同一棵子樹內or不在同一顆子樹內】那么我們就可以得出一個大致框架:記錄每個子樹內的到子樹【我們遞歸處理的樹】根節點距離值,然后從小到大排一個序,就可以計算出符合dist(a,b)<=k的點對個數,用這種方法對每一個子樹計一個res表示合法點對數這個時候要注意:對于一棵這樣的樹 ,由于遞歸的緣故,會有重復計算的情況所以我們的結果ans=ans-sigama res的【即:所有滿足合法的點對-在同一個子樹的點對數】以下是AC代碼:=v=
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define inf 0x7fffffff#define maxn 10010using namespace std;struct node{	int v,w,nxt;}e[maxn*4];int n,k;int vis[maxn];int dis[maxn],dep[maxn];int size[maxn],f[maxn];int head[maxn],cnt;int rt,cd;void add(int u,int v,int w){	e[++cnt].v=v;	e[cnt].w=w;	e[cnt].nxt=head[u];	head[u]=cnt;}void getroot(int x,int fa,int sum){	size[x]=1;f[x]=0;	for(int i=head[x];i!=-1;i=e[i].nxt){		int v=e[i].v;		if(!vis[v] && v!=fa){			getroot(v,x,sum);			size[x]+=size[v];			f[x]=max(f[x],size[v]);		}	}	f[x]=max(f[x],sum-size[x]);	if(f[x]<f[rt])rt=x;	}void getdeep(int x,int fa){	dis[++cd]=dep[x];	for(int i=head[x];i!=-1;i=e[i].nxt){		int v=e[i].v;		if(!vis[v] && v!=fa){			dep[v]=dep[x]+e[i].w;			getdeep(v,x);		}	}}int work(int x,int val){	dep[x]=val;cd=0;	getdeep(x,0);	sort(dis+1,dis+cd+1);	int res=0,l=1,r=cd;	while(l<r){		if(dis[l]+dis[r]<=k)res+=r-l,l++;		else r--;	}	return res;}int ans;void solve(int x){	ans+=work(x,0);	vis[x]=1;	for(int i=head[x];i!=-1;i=e[i].nxt){		int v=e[i].v;		if(!vis[v]){			ans-=work(v,e[i].w);			rt=0;			getroot(v,rt,size[v]);			solve(rt);		}	}}int main(){	while(~scanf("%d%d",&n,&k)){		if(n==0 && k==0)break;		ans=0,rt=0;		memset(head,-1,sizeof head);memset(vis,0,sizeof vis);		cnt=0;		memset(size,0,sizeof size);		for(int i=1;i<n;i++){			int u,v,w;scanf("%d%d%d",&u,&v,&w);			add(u,v,w);add(v,u,w);		}		f[0]=inf;		getroot(1,0,n);		solve(rt);		printf("%d/n",ans);	}	return 0;}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 寿阳县| 齐河县| 昭通市| 万载县| 宝应县| 华池县| 辉南县| 胶州市| 天津市| 石狮市| 监利县| 改则县| 莱州市| 汶上县| 崇阳县| 洪泽县| 麻阳| 永寿县| 正阳县| 滦平县| 保山市| 南阳市| 水富县| 革吉县| 石泉县| 贵州省| 延安市| 翁源县| 彭山县| 宁南县| 四川省| 理塘县| 应城市| 庐江县| 平乡县| 贡觉县| 本溪| 明光市| 鱼台县| 叙永县| 平果县|