点分治の詳細
10206 ワード
点分治の詳細
点分治は自分で導き出すアルゴリズムですが、板がありますが、Calという関数はテーマによって変わります.
点分治は、ツリー上の評価を解決するアルゴリズムであり、例えば、1本のツリー上の経路距離(u,v)距離<=K距離(u,v)距離<=Kの点対数である.
私たちはまず最も愚かな考えを考えます.
パスの長さを求めてから、満たされていないパスの長さ(つまり、最近の共通の祖先が付いていないパスの長さ)を減算することができます.
DFSはサブツリーを列挙し、DFSでこのツリーのパス長−−−が満たされていないものを一度に計算し、ソートして答えを探す.
これは効率的に見えますねO(Nlog 2 N)O(Nlog 2 N)ですが、1つのデータに対しては遅くなります.チェーン.木が鎖に退化すると,時間的複雑さはO(N 2)O(N 2)である.
したがって,点分治の考え方は,毎回木の深さが平均的であること,すなわち最大サブツリーの最小点をルートノードとして保証する.
実はこのようにして、馬鹿な考えの最適化に対して.
次の例題を見てみましょう.
POJ1741
【テーマ大意】
ツリー上の点対距離はKに等しい個数より小さい.
変数について
まずルートノードを見つけます
子ノードの大きさは求めやすいですが、親ノードがある子ツリーの大きさはどうしますか?
実はよく求めて、木の大きさ−−xの子の木の大きさ.
それから経路の長さを求めて、それではDFSはブラシを落とすことができます
次は計算です
サブツリーの列挙
完全なコードを貼り付けます.
転載先:https://www.cnblogs.com/XSamsara/p/9248290.html
点分治は自分で導き出すアルゴリズムですが、板がありますが、Calという関数はテーマによって変わります.
点分治は、ツリー上の評価を解決するアルゴリズムであり、例えば、1本のツリー上の経路距離(u,v)距離<=K距離(u,v)距離<=Kの点対数である.
私たちはまず最も愚かな考えを考えます.
パスの長さを求めてから、満たされていないパスの長さ(つまり、最近の共通の祖先が付いていないパスの長さ)を減算することができます.
DFSはサブツリーを列挙し、DFSでこのツリーのパス長−−−が満たされていないものを一度に計算し、ソートして答えを探す.
これは効率的に見えますねO(Nlog 2 N)O(Nlog 2 N)ですが、1つのデータに対しては遅くなります.チェーン.木が鎖に退化すると,時間的複雑さはO(N 2)O(N 2)である.
したがって,点分治の考え方は,毎回木の深さが平均的であること,すなわち最大サブツリーの最小点をルートノードとして保証する.
実はこのようにして、馬鹿な考えの最適化に対して.
次の例題を見てみましょう.
POJ1741
【テーマ大意】
ツリー上の点対距離はKに等しい個数より小さい.
変数について
int n,K;//
int Rot,RotSize;// ,
int Siz[MAXN];// x
int dst[MAXN];//
int Maxs[MAXN];//x
LL Ans;//
vector<int> Now;//
bool vis[MAXN];
struct Edge{//
int tot,lnk[MAXN],son[MAXN<<1],nxt[MAXN<<1],W[MAXN<<1];
void clean(){memset(lnk,0,sizeof(lnk));tot=0;}
void Add(int x,int y,int z){son[++tot]=y;W[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
まずルートノードを見つけます
子ノードの大きさは求めやすいですが、親ノードがある子ツリーの大きさはどうしますか?
実はよく求めて、木の大きさ−−xの子の木の大きさ.
void Get_Rot(int x,int fa){
Siz[x]=1;Maxs[x]=0;
for(int j=E.lnk[x];j;j=E.nxt[j])
if(!vis[E.son[j]]&&E.son[j]!=fa){
Get_Rot(E.son[j],x);
Siz[x]+=Siz[E.son[j]];
Maxs[x]=max(Siz[E.son[j]],Maxs[x]);
}
Maxs[x]=max(Maxs[x],RotSize-Siz[x]);
if(Maxs[x]
それから経路の長さを求めて、それではDFSはブラシを落とすことができます
void Get_Dst(int x,int f){
Siz[x]=1;Now.push_back(dst[x]);
for(int j=E.lnk[x];j;j=E.nxt[j])
if(E.son[j]!=f&&!vis[E.son[j]]){
dst[E.son[j]]=dst[x]+E.W[j];
Get_Dst(E.son[j],x);Siz[x]+=Siz[E.son[j]];
}
}
次は計算です
int Cal(int x,int y){
int Ret=0;
Now.clear();dst[x]=y;Get_Dst(x,0);//
sort(Now.begin(),Now.end());// <=K
for(int l=0,r=Now.size()-1;lwhile(Now[l]+Now[r]>K&&lreturn Ret;
}
サブツリーの列挙
void Solve(int x){
Ans+=Cal(x,0);vis[x]=1;// ,
for(int j=E.lnk[x];j;j=E.nxt[j])
if(!vis[E.son[j]]){
Ans-=Cal(E.son[j],E.W[j]);//
Maxs[0]=RotSize=Siz[E.son[j]];Rot=0;
Get_Rot(E.son[j],0);Solve(Rot);
}
}
完全なコードを貼り付けます.
#include
#include
#include
#include
#include
#define MAXN 10005
#define LL long long
using namespace std;
int n,K,Rot,RotSize;
int Siz[MAXN],dst[MAXN],Maxs[MAXN];LL Ans;
vector<int> Now;
bool vis[MAXN];
struct Edge{
int tot,lnk[MAXN],son[MAXN<<1],nxt[MAXN<<1],W[MAXN<<1];
void clean(){memset(lnk,0,sizeof(lnk));tot=0;}
void Add(int x,int y,int z){son[++tot]=y;W[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
void Get_Rot(int x,int fa){
Siz[x]=1;Maxs[x]=0;
for(int j=E.lnk[x];j;j=E.nxt[j])
if(!vis[E.son[j]]&&E.son[j]!=fa){
Get_Rot(E.son[j],x);
Siz[x]+=Siz[E.son[j]];
Maxs[x]=max(Siz[E.son[j]],Maxs[x]);
}
Maxs[x]=max(Maxs[x],RotSize-Siz[x]);
if(Maxs[x]void Get_Dst(int x,int f){
Siz[x]=1;Now.push_back(dst[x]);
for(int j=E.lnk[x];j;j=E.nxt[j])
if(E.son[j]!=f&&!vis[E.son[j]]){
dst[E.son[j]]=dst[x]+E.W[j];
Get_Dst(E.son[j],x);Siz[x]+=Siz[E.son[j]];
}
}
int Cal(int x,int y){
int Ret=0;
Now.clear();dst[x]=y;Get_Dst(x,0);
sort(Now.begin(),Now.end());
for(int l=0,r=Now.size()-1;lwhile(Now[l]+Now[r]>K&&lreturn Ret;
}
void Solve(int x){
Ans+=Cal(x,0);vis[x]=1;
for(int j=E.lnk[x];j;j=E.nxt[j])
if(!vis[E.son[j]]){
Ans-=Cal(E.son[j],E.W[j]);
Maxs[0]=RotSize=Siz[E.son[j]];Rot=0;
Get_Rot(E.son[j],0);Solve(Rot);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("POJ1741.in","r",stdin);
freopen("POJ1741.out","w",stdout);
#endif
while(scanf("%d%d",&n,&K),n||K){
memset(vis,0,sizeof(vis));
E.clean();
for(int i=1;iint x,y,z;scanf("%d%d%d",&x,&y,&z);
E.Add(x,y,z);E.Add(y,x,z);
}
Ans=0;Maxs[0]=RotSize=n;Rot=0;
Get_Rot(1,0);Solve(Rot);
printf("%lld
",Ans);
}
return 0;
}
転載先:https://www.cnblogs.com/XSamsara/p/9248290.html