almost 4 years ago

点分治:主要解决的是树上满足某种要求的路径问题

原理就是不断找树的重心,子树的重心,递归下去,这样每一步我们只需要考虑过根节点的路径,如何处理出这种路径的答案
因为每次都是找树的重心,所以复杂度是解决根节点路径问题的复杂度*logn
所以重点就变成了如何处理过根路径  

找重心的代码 PAY ATTENTION!

如果重心没有找好就很容易tle
PAY ATTENTION:1、tot是这个子树的节点个数 2、fa一开始传入可以是一个不存在的点

record=inf;
inline void findroot(int x,int fa)
{
    size[x]=1;int maxx=0;
    for (int k=point[x];k!=-1;k=next[k])
     if (can[k]&&v[k]!=fa)
     {
        findroot(v[k],x);
        size[x]+=size[v[k]];
        maxx=max(maxx,size[v[k]]);
     }
    maxx=max(tot-size[x],maxx);
    if (maxx<record) record=maxx,root=x;
}

poj1741 Tree

题目大意:给出N(1 <= N <= 10000)个结点的树,求使得路径u -> v长度不超过k的点对(u, v)的个数。
sol:过根路径:搜索得到子树到根节点的距离,再扫一遍得到和
这样统计出的值中会有一棵子树中来的,还需要搜一遍减去
复杂度:O(nlog^2n) 这里把calc里的快拍改成归并可以变成O(nlogn)
wrong:tle很久,是因为这里求重心求错了,在子树中求重心tot=size[子树]

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define maxn 10101 
#define maxm 20101
#define inf 1000000000
using namespace std;
int a[maxn],d[maxn],next[maxm],point[maxn],v[maxm],w[maxm],size[maxn];
int ans=0,n,m,widen=-1,record,root,an,tot;
bool can[maxm];
inline int readln()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return result*bj;
}
inline void addedge(int x,int y,int z)
{
    widen++;next[widen]=point[x];point[x]=widen;
    v[widen]=y;w[widen]=z;
    widen++;next[widen]=point[y];point[y]=widen;
    v[widen]=x;w[widen]=z;
}
inline void findroot(int now,int fa)
{
    int maxx=0,k;
    size[now]=1;
    for (k=point[now];k!=-1;k=next[k])
    if (can[k]&&v[k]!=fa)
    {
        findroot(v[k],now);
        size[now]+=size[v[k]];
        maxx=max(size[v[k]],maxx);
    }
    maxx=max(maxx,tot-size[now]);
    if (maxx<record) root=now,record=maxx;
}
inline void dfs(int now,int fa)
{
    a[++an]=d[now];
    for (int k=point[now];k!=-1;k=next[k])
        if (can[k]&&v[k]!=fa)
        {
            d[v[k]]=d[now]+w[k];
            dfs(v[k],now);
        }
}
inline int calc(int now,int value)
{
    an=0;int temp=0;
    d[now]=value;
    dfs(now,0);
    sort(a+1,a+an+1);
    for (int l=1,r=an;l<r;)
      if (a[l]+a[r]<=m) temp+=r-l++;
      else r--;
    return temp;
}
inline void search(int now)
{
    ans+=calc(now,0);
    for (int k=point[now];k!=-1;k=next[k])
    if (can[k])
    {
        can[k^1]=false;
        ans-=calc(v[k],w[k]);
        record=inf;tot=size[v[k]];
        findroot(v[k],now);
        search(root);
    }
}
inline int work()
{
    record=inf;tot=n;
    findroot(1,0);
    search(root);
}
int main()
{
    int i,u,v,w;
    while (true)
    {
        memset(point,-1,sizeof(point));
        memset(next,-1,sizeof(next));
        memset(can,true,sizeof(can));
        widen=-1;ans=0;
        n=readln();m=readln();
        if (n==0&&m==0) return 0;
        for (i=1;i<=n-1;i++) 
        {
            u=readln();v=readln();w=readln();
            addedge(u,v,w);
        }
        work();
        printf("%d\n",ans);
    }
}

bzoj2599

题意:给出N(1 <= N <= 200000)个结点的树,求长度等于K(1 <= K <= 1000000)的路径的最小边数。
sol:过根路径:一棵子树一颗子树的处理,搜出这颗子树中的距离以及经过几条边。如果k-dis满足,那么尝试更新答案
判断满足可以用一个color[]来记录这个值是否可以达到,因为k并不大
在处理完之后还需要用这颗子树得到的dis和e来更新color和c 其中c记录的是达到这个值最少需要几条边
因为已经每棵子树分开处理,所以不必要去重
复杂度:O(nlogn)
wrong:求重心 编号从0开始不能把0当空结点,应该用-1

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define maxn 200001
#define maxm 400001
#define maxk 1000001
#define inf 1000000000
using namespace std;
int next[maxm],point[maxn],v[maxm],w[maxm];
int n,m,widen=-1;
int c[maxk],color[maxk],d[maxn],e[maxn],size[maxn];
bool can[maxm];
int record,root,tot,ans=inf;
inline void addedge(int x,int y,int z)
{
    widen++;next[widen]=point[x];point[x]=widen;v[widen]=y;w[widen]=z;
    widen++;next[widen]=point[y];point[y]=widen;v[widen]=x;w[widen]=z;
}
inline void findroot(int x,int fa)
{
    size[x]=1;int maxx=0;
    for (int k=point[x];k!=-1;k=next[k])
     if (can[k]&&v[k]!=fa)
     {
        findroot(v[k],x);
        size[x]+=size[v[k]];
        maxx=max(maxx,size[v[k]]);
     }
    maxx=max(tot-size[x],maxx);
    if (maxx<record) record=maxx,root=x;
}
inline void dfs1(int now,int fa)
{
    if (d[now]>m) return;
    if (color[m-d[now]]==root) ans=min(ans,c[m-d[now]]+e[now]);
    for (int k=point[now];k!=-1;k=next[k])
      if (v[k]!=fa&&can[k])
      {
        d[v[k]]=d[now]+w[k];e[v[k]]=e[now]+1;
        dfs1(v[k],now);
      }
}
inline void dfs2(int now,int fa)
{
    if (d[now]>m)return;
    if (color[d[now]]==root) c[d[now]]=min(c[d[now]],e[now]);
    else color[d[now]]=root,c[d[now]]=e[now];
    for (int k=point[now];k!=-1;k=next[k])
        if (v[k]!=fa&&can[k])
            dfs2(v[k],now);
}
inline void work(int now)
{
    color[0]=now;c[0]=0;
    for (int k=point[now];k!=-1;k=next[k])
        if (can[k])
        {
            d[v[k]]=w[k];e[v[k]]=1;
            dfs1(v[k],now);
            dfs2(v[k],now);
        }
    for (int k=point[now];k!=-1;k=next[k])
    if (can[k])
    {
        can[k^1]=false;
        record=inf;tot=size[v[k]];
        findroot(v[k],-1);
        work(root);
    }
}
inline int readln()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return result*bj;
}
int main()
{
    int x,y,z,i;
    memset(color,-1,sizeof(color));
    memset(point,-1,sizeof(point));
    memset(next,-1,sizeof(next));
    memset(can,true,sizeof(can));
    n=readln();m=readln();
    for (i=1;i<n;i++)
    {
        x=readln();y=readln();z=readln();
        addedge(x,y,z);
    }
    record=inf;tot=n;
    findroot(0,-1);
    work(root);
    if (ans==inf)printf("-1\n");
    else printf("%d\n",ans);
}
← 【bzoj1455】【左偏树模板】【并查集】罗马游戏 mobius反演 gcd相关 数学分块 →
 
comments powered by Disqus