點分治板子_精品.doc

                1. 1、本文檔共5頁,可閱讀全部內容。
                2. 2、本文檔內容版權歸屬內容提供方,所產生的收益全部歸內容提供方所有。如果您對本文有版權爭議,可選擇認領,認領后既往收益都歸您。
                3. 3、本文檔由用戶上傳,本站不保證質量和數量令人滿意,可能有諸多瑕疵,付費之前,請仔細先通過免費閱讀內容等途徑辨別內容交易風險。如存在嚴重掛羊頭賣狗肉之情形,可聯系本站下載客服投訴處理。
                4. 文檔侵權舉報電話:19940600175。
                點分治 例題1: 一棵n個點的有邊權的樹,問你滿足x到y距離小于等于k的無序點對(x,y)的個數是多少(poj1741) typedef long long ll; const int N=2e4+5; const int inf=0x3f3f3f3f; struct Edge { int u,v,w,next; }edges[N]; int head[N],cnt; int sz[N],vis[N],root,mx,len; int q[N],r,d[N]; int k; void addEdge(int u,int v,int w) { edges[cnt].u=u; edges[cnt].v=v; edges[cnt].w=w; edges[cnt].next=head[u]; head[u]=cnt++; } void findrt(int u,int fa) { sz[u]=1; int ma=0; for(int i=head[u];~i;i=edges[i].next) { int v=edges[i].v; if(v==fa||vis[v])continue; findrt(v,u); sz[u]+=sz[v]; ma=max(ma,sz[v]); } ma=max(ma,len-sz[u]); if(ma<mx) { mx=ma; root=u; } } void getdis(int u,int fa) { q[++r]=d[u]; for(int i=head[u];~i;i=edges[i].next) { int v=edges[i].v; if(v==fa||vis[v])continue; d[v]=d[u]+edges[i].w; getdis(v,u); } } ll solve(int u,int val) { r=0; d[u]=val; getdis(u,0); ll sum=0,l=1; sort(q+1,q+1+r); while(l<r) { if(q[l]+q[r]<=k) { sum+=r-l; l++; } else r--; } return sum; } ll ans; void divide(int u) { ans+=solve(u,0); vis[u]=1; for(int i=head[u];~i;i=edges[i].next) { int v=edges[i].v; if(vis[v])continue; ans-=solve(v,edges[i].w); mx=inf; len=sz[v]; findrt(v,0); divide(root); } } int main() { int n; while(scanf("%d%d",&n,&k)) { if(n+k==0)break; cnt=0; for(int i=0;i<=n;i++) { head[i]=-1; vis[i]=0; } for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addEdge(u,v,w); addEdge(v,u,w); } ans=0; len=n; mx=inf; findrt(1,0); divide(root); printf("%lld\n",ans); } return 0; } 例題2: 一棵n個點的有邊權的樹,問你滿足x到y距離%3==0的無

                文檔評論(0)

                132****0947
                熱愛生活,加油掙錢,分享計算機專業文檔!

                相關文檔

                相關課程推薦

                全民乐