【BZOJ2555】SubString

【BZOJ2600】【IOI2011】Rice Hub

【BZOJ2599】【IOI2011】Race

Zarxdy34 posted @ 2016年4月12日 11:37 in BZOJ with tags 点分治 , 688 阅读

裸的点分治，每次DFS暴力更新就好了。

BZOJ2599
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79	`#include <cstdio>` `#include <cstring>` `#include <algorithm>` `using` `namespace` `std;` `const` `int` `maxn=200010,maxk=1000010,inf=~0U>>1;` `int` `head[maxn],next[maxn<<1],E[maxn<<1],D[maxn<<1],Ecnt;` `int` `sons[maxn];` `int` `f[maxk],po[maxk];` `int` `vis[maxk];` `int` `root,rootsize;` `int` `n,k,ans;` `void` `Add_Edge(int` `x,int` `y,int` `dis) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;D[Ecnt]=dis;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;D[Ecnt]=dis;}` `int` `Q[maxn],Qf[maxn],Qtop;` `void` `Solve_DFS(int` `x,int` `dis,int` `dep,int` `fa)` `{` `if` `(dis>k)` `return;` `Q[Qtop]=dis;Qf[Qtop]=dep;Qtop++;` `for` `(int` `i=head[x];i;i=next[i])` `if` `(!vis[E[i]] && E[i]!=fa)` `Solve_DFS(E[i],dis+D[i],dep+1,x);` `}` `void` `Solve(int` `x)` `{` `po[0]=x;` `for` `(int` `i=head[x];i;i=next[i])` `if` `(!vis[E[i]])` `{` `Qtop=0;` `Solve_DFS(E[i],D[i],1,x);` `for` `(int` `j=0;j<Qtop;j++)` `if` `(po[k-Q[j]]==x && Qf[j]+f[k-Q[j]]<ans) ans=Qf[j]+f[k-Q[j]];` `for` `(int` `j=0;j<Qtop;j++)` `{` `if` `(po[Q[j]]!=x) po[Q[j]]=x,f[Q[j]]=Qf[j];` `else` `if` `(Qf[j]<f[Q[j]]) f[Q[j]]=Qf[j];` `}` `}` `}` `int` `FindRoot(int` `x,int` `fa,int` `N)` `{` `int` `tsize=0;` `sons[x]=0;` `for` `(int` `i=head[x];i;i=next[i])` `if` `(E[i]!=fa && !vis[E[i]])` `{` `int` `tsons=FindRoot(E[i],x,N);` `sons[x]+=tsons;` `if` `(tsons>tsize) tsize=tsons;` `}` `if` `(N-sons[x]-1>tsize) tsize=N-sons[x]-1;` `if` `(rootsize>tsize) root=x,rootsize=tsize;` `return` `sons[x]+1;` `}` `void` `Divide_DFS(int` `x,int` `N)` `{` `if` `(N==1)` `return;` `root=x;rootsize=n;` `FindRoot(x,0,N);` `x=root;` `Solve(x);` `vis[x]=1;` `for` `(int` `i=head[x];i;i=next[i])` `if` `(!vis[E[i]])` `if` `(sons[E[i]]<sons[x]) Divide_DFS(E[i],sons[E[i]]);else` `Divide_DFS(E[i],N-sons[x]);` `}` `void` `read(int` `&x) {char` `ch;while` `((ch=getchar())<'0'` `\|\| ch>'9');x=ch-'0';while` `((ch=getchar())<='9'` `&& ch>='0') x=x*10+ch-'0';}` `int` `main()` `{` `read(n),read(k);` `for` `(int` `i=0,x,y,c;i<n-1;i++) read(x),read(y),read(c),x++,y++,Add_Edge(x,y,c);` `ans=inf;` `Divide_DFS(1,n);` `if` `(ans==inf)` `puts("-1");else` `printf("%d\n",ans);` `return` `0;` `}`

评论 (0)