[SDOI2017]天才黑客
傳送門
Description
給出一張帶邊權的有向圖，每個邊都上都有一個字符串（給出對應Trie樹上的節點），一條路徑的長度為路徑上的邊權之和+相鄰兩條邊的字符串的lcp長度之和。
求從1到其它節點的最短路
Solution
預備部分
首先，兩個字符串的lcp，就是對應節點在Trie樹上的lca的深度值。
把每條邊拆成兩對入點和出點，分別是\(r1,r2,c1,c2\)，它們之間的邊權值都是原來的邊權：
大概像這樣？[圖1]
建一個源點S，向所有原先入點是1的點連邊權為0的邊
然后枚舉原圖中的每個點\(x\),把所有形如\(<i,x>,<x,j>\)的邊都連接在一起，使得邊權就是兩兩字符串的\(lcp\)大小
求出原圖對于源點的最短路
最后，對于一個點\(x\)，枚舉所有\(<i,x>\)的邊，取它們中出點最小的\(dis\)
可是一個點的入邊和出邊會有很多，所以連出的邊數大概是是\(O(n^2)\)的，顯然不行
所以我們考慮優化建圖：
接下來介紹前后綴優化建圖
首先，之前把一條邊拆成兩對出點和入點，其中一對用來處理后綴，一對用來處理前綴
對于一個點，我們以前綴為例子：
按照每條邊對應字符串在Trie樹上的\(dfs\)序排序，上面是入邊（\(c1\)點），下面是出邊（\(r1\)點）：
[圖2]
上下分別按照順序連邊權為\(0\)的有向邊
[圖3]
考慮到一個性質\(lcp(a_1,a_n)=\min_{i=1}^{n-1} lcp(a_i,a_i+1)\)
考慮dfs序相鄰的兩點\(x_i,x_{i+1}\)（有可能都是入點或出點），計算出\(lcp(x_i,x_{i+1})\)，考慮它們的影響范圍，顯然，我們找到序號最大且小于等于\(i\)的入邊\(c1_k\)和序號大于等于\(i+1\)的出邊\(r1_j\)，連邊\(<c1_k,r1_j>\)，長度為\(lcp(x_i,x_{i+1})\)
[圖4]
這樣，就可以滿足一個序號小的入邊到任意一個序號比它大的出邊之間的最短路就是它們的\(lcp\)值
這是前綴優化，當然后綴優化部分與之類似，這里就不再贅述
最后，分享一下最短路的寫法，貌似也不會快多少吧。。。
const ll nN=262144,inf=20000000000;
ll d[MM<<2];
struct node{ll x;int f;}t[nN<<1];
inline node Min(const node&o,const node&oo){return o.x<oo.x?o:oo;}
inline void rw(int k,ll x){for(t[k+=nN].x=x;k>>=1;)t[k]=Min(t[k<<1],t[k<<1|1]);}
inline void dij()
{reg int i,x;++tt;for(i=cc[1].size()-1;~i;--i)Ins(tt,cc[1][i]*4-3,0),Ins(tt,cc[1][i]*4-1,0);for(i=1;i<nN<<1;++i) t[i].x=inf;for(i=1;i<=tt;++i) d[t[i+nN].f=i]=inf;for(rw(tt,d[tt]=0);t[1].x!=inf;){rw(x=t[1].f,inf);for(i=hr[x];i;i=e[i].nex)if(d[e[i].to]>d[x]+e[i].w)rw(e[i].to,d[e[i].to]=d[x]+e[i].w);}
}Code?
#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f;
}
#define reg register
#define ME(x) memset(x,0,sizeof x)
const int MK=20005,MN=50005,MM=50005;
int N,M,K,dfn[MK];
class Tire
{private: int fa[MK],dep[MK],top[MK],mx[MK],siz[MK],dind;struct ed{int to,nex;}e[MK];int hr[MK],en,vis[MK];inline void Ins(int x,int y){e[++en]=(ed){y,hr[x]};hr[x]=en;}void dfs1(int x,int d){dep[x]=d;siz[x]=1;for(reg int i=hr[x];i;i=e[i].nex)dfs1(e[i].to,d+1),siz[x]+=siz[e[i].to],(siz[e[i].to]>siz[mx[x]])?mx[x]=e[i].to:0;}void dfs2(int x,int tp){top[x]=tp;if(mx[x])dfs2(mx[x],tp);dfn[x]=++dind;for(reg int i=hr[x];i;i=e[i].nex)if(e[i].to^mx[x])dfs2(e[i].to,e[i].to);}public:inline void init(){ME(vis);ME(hr);ME(fa);ME(dep);ME(top);ME(mx);ME(siz);en=dind=0;}inline void ins(int x,int y,int w){Ins(x,y);fa[y]=x;}inline void build(){dfs1(1,0);dfs2(1,1);}inline int lca(int x,int y){for(;top[x]^top[y];)dep[top[x]]<dep[top[y]]?y=fa[top[y]]:x=fa[top[x]];return min(dep[x],dep[y]);}
}trie;
int tt;
struct edge{int to,w,nex;}e[MM*20];int en,hr[MM<<2];
int pos[MM],idt;
bool cmp(const int&o,const int&oo){return dfn[pos[std::abs(o)]]<dfn[pos[std::abs(oo)]];}
std::vector<int> rr[MN],cc[MN];
int tmp[MM],nn;
inline void Ins(int x,int y,int c){e[++en]=(edge){y,c,hr[x]};hr[x]=en;}
inline void ins(int x,int y,int c,int w)
{pos[++idt]=w;Ins(tt+1,tt+2,c);Ins(tt+1,tt+4,c);Ins(tt+3,tt+2,c);Ins(tt+3,tt+4,c);rr[y].push_back(idt);cc[x].push_back(idt);tt+=4;
}
inline void Build(int x)
{if(!rr[x].size()||!cc[x].size()) return;std::sort(rr[x].begin(),rr[x].end(),cmp);std::sort(cc[x].begin(),cc[x].end(),cmp);reg int t,i,j,len;nn=0;for(i=rr[x].size()-1;i>0;--i)Ins(rr[x][i-1]*4-2,rr[x][i]*4-2,0),Ins(rr[x][i]*4,rr[x][i-1]*4,0);for(i=cc[x].size()-1;i>0;--i)Ins(cc[x][i-1]*4-3,cc[x][i]*4-3,0),Ins(cc[x][i]*4-1,cc[x][i-1]*4-1,0);for(i=cc[x].size()-1;~i;--i) tmp[++nn]=-cc[x][i];for(i=rr[x].size()-1;~i;--i) tmp[++nn]=rr[x][i];std::sort(tmp+1,tmp+nn+1,cmp);for(t=1,i=j=0;t<nn;++t) {if(tmp[t]<0)++j,tmp[t]=-tmp[t];else ++i;len=trie.lca(pos[std::abs(tmp[t])],pos[std::abs(tmp[t+1])]);if(i!=0&&j!=cc[x].size())Ins(rr[x][i-1]*4-2,cc[x][j]*4-3,len);if(j!=0&&i!=rr[x].size())Ins(rr[x][i]*4,cc[x][j-1]*4-1,len);}
}
const ll nN=262144,inf=20000000000;
ll d[MM<<2];
struct node{ll x;int f;}t[nN<<1];
inline node Min(const node&o,const node&oo){return o.x<oo.x?o:oo;}
inline void rw(int k,ll x){for(t[k+=nN].x=x;k>>=1;)t[k]=Min(t[k<<1],t[k<<1|1]);}
inline void dij()
{reg int i,x;++tt;for(i=cc[1].size()-1;~i;--i)Ins(tt,cc[1][i]*4-3,0),Ins(tt,cc[1][i]*4-1,0);for(i=1;i<nN<<1;++i) t[i].x=inf;for(i=1;i<=tt;++i) d[t[i+nN].f=i]=inf;for(rw(tt,d[tt]=0);t[1].x!=inf;){rw(x=t[1].f,inf);for(i=hr[x];i;i=e[i].nex)if(d[e[i].to]>d[x]+e[i].w)rw(e[i].to,d[e[i].to]=d[x]+e[i].w);}
}
inline ll getans(int x)
{reg ll i,ans=inf;for(i=rr[x].size()-1;~i;--i)ans=min(ans,min(d[rr[x][i]*4-2],d[rr[x][i]*4]));return ans;
}
inline void init()
{nn=tt=en=idt=0;ME(hr);ME(pos);ME(tmp);ME(dfn);for(reg int i=1;i<=N;++i) rr[i].clear(),cc[i].clear();
}
int main()
{reg int T=read();while(T--) {N=read(),M=read(),K=read();trie.init();reg int i,x,y,c;for(i=1;i<=M;++i) x=read(),y=read(),c=read(),ins(x,y,c,read());for(i=1;i<K;++i) x=read(),y=read(),trie.ins(x,y,read()); trie.build();for(i=2;i<=N;++i) Build(i);dij();for(i=2;i<=N;++i) printf("%lld\n",getans(i));init();}
}Blog來自PaperCloud，未經允許，請勿轉載，TKS！
轉載于:https://www.cnblogs.com/PaperCloud/p/sdoi2017_hacks.html
總結
以上是生活随笔為你收集整理的[SDOI2017]天才黑客的全部內容，希望文章能夠幫你解決所遇到的問題。
