[NOI2011] 道路修建

这道题要卡空间 128M。。。

于是本来可以 DFS 的栈空间就爆了。。。

法一:玄学底层 +DFS 传参优化。。。

法二:直接拓扑。

我们从叶结点开始拓扑,处理完之后删点,然后将新一轮的叶结点拓扑,逐渐逼近根结点,直
到队列为空。

因为是从叶结点开始遍历,所以可以自底向上处理子树大小,拓扑的过程中累加答案即可。
空间优化到 40M

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000006;

int n;
struct qxx{int nex,t;ll v;};// 链式前向星
qxx e[N*2];
int head[N],cnt;
int dg[N],sz[N];//dgree,size
bool vis[N];
void add_path(int f,int t,int v){
    e[++cnt]=(qxx){head[f],t,v};
    head[f]=cnt;
}
queue<int> q;
ll ans;

int main(){
    scanf("%d",&n);
    for(int i=1,a,b,c;i<n;i++){
        scanf("%d%d%d",&a,&b,&c);
        add_path(a,b,c);
        add_path(b,a,c);
        ++dg[a],++dg[b];
    }
    for(int i=1;i<=n;i++){
        sz[i]=1;
        if(dg[i]==1)q.push(i);// 度为 1 的结点即为根结点
    }
    while(!q.empty()){// 队中都是度为 1 的点
        int k=q.front();q.pop();
        vis[k]=true;// 已出队的标记为已访问
        for(int i=head[k];i;i=e[i].nex){
            if(!vis[e[i].t]){// 这个点是唯一的
                ans+=abs(n-sz[k]*2)*e[i].v;
                sz[e[i].t]+=sz[k];
                dg[e[i].t]--;// 删点
                if(dg[e[i].t]==1){
                    q.push(e[i].t);
                }
            }
        }
    }
    printf("%lld",ans);
    return 0;
}

注意,这里的拓扑要等到结点出队的时候再标记访问,因为在队列里的结点仍可能被访问到。


  转载请注明: Sshwy's Blog [NOI2011] 道路修建

 上一篇
[NOIP2013] 货车运输 [NOIP2013] 货车运输
本题关注路径上最小边权的值最大,则在图上生成一颗最大生成树,在树上跑 LCA 即可。 顺便练一下 Prim 用线段树维护最大值,树剖求 LCA. 注意非连通图的处理。 复杂度 ```cppincludein
2018.10.01
下一篇 
后缀数组 后缀数组
摘要 后缀数组由 Manber & Myers 在 1990 年首先提出《Suffix arrays: a new method for on-line string searches》,用以替代后缀树,并且改进了存储空间的需求。
2018.10.01
  目录