当前位置：首页 > 入侵接单 > 正文内容

黑客教你定位手机芯片&nbsp;&nbsp;BZOJ4912

访客3年前 (2022-04-21)入侵接单363

树立新图，本图外每一条边正在新图外是点，点权为$w_i$，边权为二个字符串的LCP。

对于字典树入止DFS，将每一个点四周一圈边对于应的字符串按DFS序从小到年夜排序。

依据后缀数组应用 height数组供LCP的道理，相似天否以获得：

令$h_i=LCP(str_i,str_{i+ 一})$，则$LCP(str_l,str_r)=\min(h_{l..r- 一})$。

列举每一个$h_i$做为分界线，这么新图外二侧的点都可以经由过程没有跨越 $h_i$的价值互相拜访。

树立一排前缀虚点战后缀虚点然后对于应先后缀之间连边便可。

如斯修图的点数战边数均为$O(m)$，空儿庞大度$O(m\log m)$。

#include<cstdio> #include<algorithm> #include<queue> #include<vector> using namespace std; typedef pair<int,int>P; const int N= 五00 一0,inf=~0U>> 一; int Case,n,m,K,i,j,x,y,z,g[N],nxt[N],size[N],f[N],d[N],son[N],loc[N],top[N],dfn; int gi[N],go[N],V[N<< 一],NXT[N<< 一],ED; int cnt,pi[N<< 一],po[N<< 一],si[N<< 一],so[N<< 一],cq,q[N<< 一]; inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<=' 九')));a=c-'0';while(((c=getchar())>='0')&&(c<=' 九'))(a*= 一0)+=c-'0';} struct E{int a,b,c,d;}e[N]; namespace G{ const int N= 四五00 一0,M= 八000 一0; int g[N],v[M],w[M],nxt[M],ed,val[N],d[N];priority_queue<P,vector<P>,greater<P> >q; inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;} inline void ext(int x,int y){ y+=val[x]; if(y<d[x])q.push(P(d[x]=y,x)); } void solve(){ for(i= 一;i<=cnt;i++)d[i]=inf; for(i= 一;i<=m;i++)if(e[i].a== 一)ext(i,0); while(!q.empty()){ P t=q.top();q.pop(); if(d[t.second]>t.first)continue; for(i=g[t.second];i;i=nxt[i])ext(v[i],t.first+w[i]); } } } inline bool cmp(int x,int y){return loc[e[abs(x)].d]<loc[e[abs(y)].d];} inline void add(int x,int y){nxt[y]=g[x];g[x]=y;} inline void ADD(int&x,int y){V[++ED]=y;NXT[ED]=x;x=ED;} void dfs(int x){ size[x]= 一; for(int i=g[x];i;i=nxt[i]){ f[i]=x,d[i]=d[x]+ 一; dfs(i),size[x]+=size[i]; if(size[i]>size[son[x]])son[x]=i; } } void dfs 二(int x,int y){ loc[x]=++dfn;top[x]=y; if(son[x])dfs 二(son[x],y); for(int i=g[x];i;i=nxt[i])if(i!=son[x])dfs 二(i,i); } inline int lca(int x,int y){ for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]<d[top[y]])swap(x,y); return min(d[x],d[y]); } inline void solve(int x){ int i; if(!gi[x]||!go[x])return; cq=0; for(i=gi[x];i;i=NXT[i])q[++cq]=V[i]; for(i=go[x];i;i=NXT[i])q[++cq]=-V[i]; sort(q+ 一,q+cq+ 一,cmp); for(i= 一;i<=cq;i++){ pi[i]=++cnt; si[i]=++cnt; po[i]=++cnt; so[i]=++cnt; if(i> 一){ G::add(pi[i- 一],pi[i],0); G::add(po[i- 一],po[i],0); G::add(si[i],si[i- 一],0); G::add(so[i],so[i- 一],0); } if(q[i]>0)G::add(q[i],pi[i],0),G::add(q[i],si[i],0); else q[i]*=- 一,G::add(po[i],q[i],0),G::add(so[i],q[i],0); } for(i= 一;i<cq;i++){ int t=lca(e[q[i]].d,e[q[i+ 一]].d); G::add(pi[i],po[i+ 一],t); G::add(si[i+ 一],so[i],t); } } int main(){ read(Case); while(Case--){ read(n),read(m),read(K); for(i= 一;i<=m;i++){ read(e[i].a),read(e[i].b),read(e[i].c),read(e[i].d); ADD(gi[e[i].b],i),ADD(go[e[i].a],i); G::val[i]=e[i].c; } cnt=m; for(i= 一;i<K;i++)read(x),read(y),read(z),add(x,y); dfs( 一),dfs 二( 一, 一); for(i= 一;i<=n;i++)solve(i); G::solve(); for(i= 二;i<=n;i++){ x=inf; for(j=gi[i];j;j=NXT[j])x=min(x,G::d[V[j]]); printf("%d\n",x); } for(i= 一;i<=cnt;i++)G::g[i]=G::val[i]=0; for(i= 一;i<=K;i++)g[i]=size[i]=f[i]=d[i]=son[i]=0; for(i= 一;i<=n;i++)gi[i]=go[i]=0; ED=dfn=G::ed=0; } return 0; }

转载于:https://www.cnblogs.com/clrs 九七/p/ 七八三三七九七.html