[NOIP2013] 货车运输

  • 本题关注路径上最小边权的值最大,则在图上生成一颗最大生成树,在树上跑 LCA 即可。
  • 顺便练一下 Prim
  • 用线段树维护最大值,树剖求 LCA.
  • 注意非连通图的处理。
  • 复杂度
    ```cpp

    include

    include

    include

    using namespace std;
    const int N=100005,M=500005;
    int n,m,Q;

int a[N],s[1<<18]; 维护最小值 void push_up(int rt){s[rt]="min(s[rt<<1],s[rt<<1|1]);}" int lst_build(int l="1,int" r="n,int" rt="1){//" 线段树 if(l="=r)return" s[rt]="a[l];" mid="(l+r)">>1;
lst_build(l,mid,rt<<1),lst_build(mid+1,r,rt<<1|1); push_up(rt); } int lst_min(int l,int r,int l="1,int" r="n,int" rt="1){if(L<=l&&r<=R)return" s[rt]; mid="(l+r)">>1,m1=0x3f3f3f3f,m2=0x3f3f3f3f;
if(L<=mid)m1=lst_min(L,R,l,mid,rt<<1);
if(mid<R)m2=lst_min(L,R,mid+1,r,rt<<1|1);
return min(m1,m2);
}

struct qxx{int nex,t,v;};
qxx e[M*2];
int h[N],cnt;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;
}

struct node{
int p,s,b,v;
int dp,sz,tp,hvs,idx;
};
node t[N];
void add_son(int p,int s,int v){t[s].p=p,t[s].b=t[p].s,t[p].s=s,t[s].v=v;
}
bool sz_vis[N];
int szdfs(int rt,int dp){t[rt].dp=dp,t[rt].sz=1,sz_vis[rt]=true;
for(int i=t[rt].s;i;i=t[i].b)t[rt].sz+=szdfs(i,dp+1);
return t[rt].sz;
}
int dfn;
void dedfs(int rt,int tp){t[rt].tp=tp,t[rt].idx=++dfn,a[dfn]=t[rt].v;
// 存储的是到父结点的路径长度
if(!t[rt].s)return;
for(int mx=0,i=t[rt].s;i;i=t[i].b)
if(mxt[y].idx)x^=y^=x^=y;
return min(res,lst_min(t[x].idx+1,t[y].idx));
//‘t[x].idx+1’舍弃了 x 连接到父结点的边
}

struct data{
int f,t,v;//v: 连接的边的权值
bool operator<(data tht)const{return v<tht.v;// 边权越大,优先级越小 }
};

int main(){scanf(“%d%d”,&n,&m);
for(int i=1;i<=m;i++){
int x,y,z;
scanf(“%d%d%d”,&x,&y,&z);
add_path(x,y,z);
add_path(y,x,z);
}
//Prim
bool vis[N]={0};
vis[0]=1;
priority_queue q;
for(int i=1;i<=n;i++){if(vis[i])continue;
q.push((data){0,i,0});//addson(0,i,0), 不会对树剖有影响
while(!q.empty()){data k=q.top();q.pop();
if(vis[k.t])continue;
vis[k.t]=1;
add_son(k.f,k.t,k.v);
for(int i=h[k.t];i;i=e[i].nex)if(!vis[e[i].t])
q.push((data){k.t,e[i].t,e[i].v});
}
}
//decomposition
for(int i=1;i<=n;i++){if(!sz_vis[i]){szdfs(i,1);
dedfs(i,i);
}
}
lst_build();
//query
scanf(“%d”,&Q);
for(int i=1;i<=Q;i++){
int x,y;
scanf(“%d%d”,&x,&y);
printf(“%d\n”,tree_query(x,y));
}
return 0;
}
```


  转载请注明: Sshwy's Blog [NOIP2013] 货车运输

 上一篇
BZOJ4010:[HNOI2015] 菜肴制作 BZOJ4010:[HNOI2015] 菜肴制作
题面 错误原因难得遇到一道题让我写错误原因。。。 错解 首先,这道题不是字典序最小,因为他从 1,2…n 依次考虑。 一开始想直接贪心遍历,从 1 号考虑,为了做 1 号,就要把它的先决菜肴都做了,于是先做价值高的先决菜肴再做第二高的,这样
2018.10.01
下一篇 
[NOI2011] 道路修建 [NOI2011] 道路修建
这道题要卡空间 128M。。。 于是本来可以 DFS 的栈空间就爆了。。。 法一:玄学底层 +DFS 传参优化。。。 法二:直接拓扑。 我们从叶结点开始拓扑,处理完之后删点,然后将新一轮的叶结点拓扑,逐渐逼近根结点,直到队列为空。 因为是
2018.10.01
  目录