BZOJ2599：[IOI2011]Race

浅谈树分治：https://www.cnblogs.com/AKMer/p/10014803.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=2599

我们设\(f_i\)为长度为\(i\)的路径边数最小可以是多少，依次遍历当前根的子树，先用\(cnt+f[k-dis]\)更新答案，再遍历第二遍当前子树更新\(f\)数组。\(cnt\)表示根到当前点一共经过了多少条边。因为\(k\)的范围是\(10^6\)级别的，每次处理当前联通块前把\(f\)数组全部赋成极大值会很慢，所以我们每次更新\(f\)数组的时候把被改动过的\(dis\)用栈记录下来，每次处理完当前联通块就弹栈并且把相应的\(f\)数组初始化，这样做就是\(O(n)\)级别的了。

如果用边分做的话，记得把新建的边权值赋成\(-1\)，因为可能会有边权为\(0\)的边，然后统计\(cnt\)的时候只有在碰到权值不为\(-1\)的边才算。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

点分治版代码如下：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=2e5+5,maxm=1e6+5;;

bool vis[maxn],insta[maxm];

int n,m,tot,mx,rt,N,ans,top;

int siz[maxn],f[maxm],sta[maxn];

int now[maxn],pre[maxn*2],son[maxn*2],val[maxn*2];

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

void add(int a,int b,int c) {

    pre[++tot]=now[a];

    now[a]=tot,son[tot]=b,val[tot]=c;

}

void find_rt(int fa,int u) {

    int res=0;siz[u]=1;

    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

        if(!vis[v]&&v!=fa)find_rt(u,v),siz[u]+=siz[v],res=max(res,siz[v]);

    res=max(res,N-siz[u]);

    if(res<mx)mx=res,rt=u;

}

void query(int fa,int u,int cnt,int dis) {

    if(dis<=m)ans=min(ans,cnt+f[m-dis]);siz[u]=1;

    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

        if(!vis[v]&&v!=fa)query(u,v,cnt+1,dis+val[p]),siz[u]+=siz[v];

}

void solve(int fa,int u,int cnt,int dis) {

    if(dis>m)return;

    f[dis]=min(f[dis],cnt);

    if(!insta[dis])sta[++top]=dis,insta[dis]=1;

    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

        if(!vis[v]&&v!=fa)solve(u,v,cnt+1,dis+val[p]);

}

void work(int u,int size) {

    N=size,mx=rt=n+1,find_rt(0,u),u=rt,vis[u]=1;

    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

        if(!vis[v])query(u,v,1,val[p]),solve(u,v,1,val[p]);

    ans=min(ans,f[m]);

    while(top) {

        f[sta[top]]=f[m+1];

        insta[sta[top--]]=0;

    }

    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

        if(!vis[v])work(v,siz[v]);

}

int main() {

    n=read(),m=read();

    for(int i=1;i<n;i++) {

        int a=read()+1,b=read()+1,c=read();

        add(a,b,c),add(b,a,c);

    }

    memset(f,127/3,sizeof(f));

    ans=f[0];work(1,n);

    if(ans==f[m+1])puts("-1");

    else printf("%d\n",ans);

    return 0;

}

边分治版代码如下：

#include <cmath>

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

using namespace std;

typedef pair<int,int> pii;

#define fr first

#define sc second

const int maxn=4e5+5,maxm=1e6+5;

bool vis[maxn],insta[maxm];

int f[maxm],siz[maxn],sta[maxn];

int n,m,tot,cnt,mx,id,N,top,ans,tmp1,tmp2;

int now[maxn],pre[maxn*2],son[maxn*2],val[maxn*2];

vector<pii>to[maxn];

vector<pii>::iterator it;

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

void add(int a,int b,int c) {

    pre[++tot]=now[a];

    now[a]=tot,son[tot]=b,val[tot]=c;

}

void find_son(int fa,int u) {

    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

        if(v!=fa)to[u].push_back(make_pair(v,val[p])),find_son(u,v);

}

void rebuild() {

    tot=1;memset(now,0,sizeof(now));

    for(int i=1;i<=cnt;i++) {

        int size=to[i].size();

        if(size<=2) {

            for(it=to[i].begin();it!=to[i].end();it++) {

                pii tmp=*it;

                add(i,tmp.fr,tmp.sc),add(tmp.fr,i,tmp.sc);

            }

        }

        else {

            pii u1=make_pair(++cnt,-1),u2;

            if(size==3)u2=to[i].front();

            else u2=make_pair(++cnt,-1);

            add(i,u1.fr,u1.sc),add(u1.fr,i,u1.sc);

            add(i,u2.fr,u2.sc),add(u2.fr,i,u2.sc);

            if(size==3) {

                for(int j=1;j<=2;j++)

                    to[cnt].push_back(to[i].back()),to[i].pop_back();

            }

            else {

                int p=0;

                for(it=to[i].begin();it!=to[i].end();it++) {

                    if(!p)to[cnt-1].push_back(*it);

                    else to[cnt].push_back(*it);p^=1;

                }

            }

        }

    }

}

void find_edge(int fa,int u) {

    siz[u]=1;

    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

        if(!vis[p>>1]&&v!=fa) {

            find_edge(u,v),siz[u]+=siz[v];

            if(abs(N-2*siz[v])<mx)mx=abs(N-2*siz[v]),id=p>>1;

        }

}

void solve(int fa,int u,int num,int dis) {

    if(dis<=m) {

        f[dis]=min(f[dis],num);

        if(!insta[dis])sta[++top]=dis,insta[dis]=1;

    }siz[u]=1;

    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

        if(!vis[p>>1]&&v!=fa)

			solve(u,v,num+(val[p]!=-1),dis+(val[p]!=-1)*val[p]),siz[u]+=siz[v];

}

void query(int fa,int u,int num,int dis) {

    if(dis+tmp1<=m)ans=min(ans,num+f[m-dis-tmp1]+tmp2);siz[u]=1;

    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

        if(!vis[p>>1]&&v!=fa)

			query(u,v,num+(val[p]!=-1),dis+(val[p]!=-1)*val[p]),siz[u]+=siz[v];

}

void work(int u,int size) {

    N=size,mx=id=cnt+1,find_edge(0,u);

    if(id==cnt+1)return;vis[id]=1;

    int u1=son[id<<1],u2=son[id<<1|1];

    tmp1=(val[id<<1]!=-1)*val[id<<1],tmp2=(val[id<<1]!=-1);

    solve(0,u1,0,0),query(0,u2,0,0);

    while(top) {

        f[sta[top]]=f[m+1];

        insta[sta[top--]]=0;

    }

    work(u1,siz[u1]),work(u2,siz[u2]);

}

int main() {

    cnt=n=read(),m=read();

    for(int i=1;i<n;i++) {

        int a=read()+1,b=read()+1,c=read();

        add(a,b,c),add(b,a,c);

    }

    find_son(0,1),rebuild();

    memset(f,127/3,sizeof(f));

    ans=f[0];work(1,cnt);

    if(ans==f[m+1])puts("-1");

    else printf("%d\n",ans);

    return 0;

}

巴特西

BZOJ2599：[IOI2011]Race

点分治版代码如下：

边分治版代码如下：

最新文章

热门文章