题解 P3783 【[SDOI2017]天才黑客】

其实愚蠢的$O(mlog^2m)$做法应该被叉掉的…… __________________ # 关于spfa ~~它死了~~ 原因是这道题你最后建出来的图就是spfa最怂的网格图，出题人甚至只需要random数据,你就自动完成了卡spfa的任务…… ~~dijkstra保平安~~ _____________ ## 本题题解 首先简化一下并不明确的题意 给出一张有向图，每个边上有边权，以及一个字符串 一条有向路径的长度为这条路径上每个边的边权之和+按照路径的顺序将这些边上的字符串排成一列，相邻两个串的lcp长度之和。 求这种长度定义下的1号点到其他点的最短路 保证边上的所有字符串都可以被一个字典树所识别，字典树的大小不会很大 那么我们仔细看一下应该还是最短路问题，所以最后肯定还是跑一遍dijkstra解决问题，现在我们的精力应该放在如何建图上 仔细看一眼你会发现这道题点在最短路当中并没有太多用处，路径长度的计算公式是和边有关的，因此我们考虑下面一个比较显然~~(?或许并不)~~的暴力建图方式 _将一个边拆成两个点，一个是入点另一个是出点，中间链接一条为这条边权值的有向边，对于两个边<a,b>,<c,d>来讲，如果b=c，那么第一个边的出点向第二个边的入点连一条权值等于两个边上字符串lcp的长度的有向边。_ _新建一个超级源点s，对于所有形如<1,a>的边，s向这些边的入点连一条边权为0的有向边_ _最后输出最短路长度的时候，对于每一个点i，枚举形如<a,i>的边，在这些边的出点的dis值中找最小值，作为这个点的最短路输出_ 好了翻译一下上边的鬼话就是我们把边看做点重新建一张图出来，边自己的权值拆成两个点保存在这两个点之间的边权中，然后边和边之间连边的边权就是边上字符串的lcp长度 遗憾的是上边的建图方式碰到下面这张图会直接爆炸……  恭喜你连了$O(m^2)$条边，然后你炸了 接下来就是奇技淫巧的优化建图时间了 如果你想了刚才那个暴力你会发现我们连了一堆边权一样的边…… 因为两个字符串的lcp长度就是这两个字符串在字典树上的lca深度，因此我们可以会发现所有可能的边权种类只有$O(m+k)$种，因此按照刚才的暴力我们一定会连出很多边权一样的边 此时我们观察了一会这个图发现一个有趣的事实 我们把每个点周围一圈的边拉出来，按照边上字符串在字典树上的dfs序排一个序，此时我们看一看会有什么有趣的现象发生呢？ 由于我们现在有了一堆按照字典序排好序的字符串，因此我们觉得这非常像后缀数组，所以我们尝试着求出相邻两个字符串的lcp长度，或者说字典树上的lca深度，或者说求出这些排好序字符串的height数组 那么我们会并不惊奇的发现一个事实，两个字符串的lcp长度就是height数组的区间最小值，区间端点为这两个字符串的位置，就像后缀数组一样的性质 如果你对后缀数组那一套足够熟练的话你会非常熟练的使用单调栈求出每一个$h_{i}$所"管辖"(也就是它是区间最小值)的范围，然后更加熟练的使用线段树优化建图完成区间链接一条权值一样的边的操作，然后以$O(mlog^2m)$的复杂度做完这道题 但是啊，让我们接着想想，线段树优化建图还有优化空间吗？ 当然有，答案是 ### 前缀和/后缀和优化建图 我们依然是把每个点周围一圈的边全部拉出去按照dfs序排序，依然处理出height数组,但是，我们不再使用单调栈，而是考虑这样一种奇技淫巧 对于某一个$h_{i}$来讲，在i左侧的入点可以通过不超过$h_{i}$代价到达i右侧出点，同理i右侧的入点可以通过不超过$h_{i}$的代价到达i右侧的出点 所以我们可以让i左侧点向i右侧点连一堆边，i右侧点向i左侧点连一堆边，当然，边权都是$h_{i}$ 此时并没有任何优化，但是假设我们只需要让i左侧点向右侧点连边，则我们可以使用这样一种奇技淫巧，我们像这样连边即可，其中上边的点是入点，底下的点是出点  很显然我们使用了很少的边就完成了连边工作 但是用这个技巧我们并无法同时支持从左向右连和从左向右连 仔细想想真的不行吗……？ #### 其实是可以的 我们将一条边拆成2个入点和两个出点，然后连成这样的形状  然后第一对出入点处理从左向右连的情况，第二对出入点处理从右向左的情况 即可 此时我们就可以建立一个超级源点连向1号点的所有出边跑一边dijkstra，之后对于每一个i，for一遍所有指向i的出边求最短路的最小值，然后我们就可以搞定这道题了 备注：建图会非常恶心……自己慢慢画图建吧……一不小心就写了100行…… ```C #include<cstdio> #include<algorithm> #include<vector> #include<queue> using namespace std; int dfn[20010];int dep[20010];int n;int m;int k;int T;typedef long long ll; namespace Tree { const int N=2*1e4+10; struct data{int v;int val;friend bool operator <(data a,data b){return a.val<b.val;}}; int fa[N][18];int df;vector <data> v[N]; inline void add(int u,int V,int w){v[u].push_back((data){V,w});} inline void dfs(int u)//dfs { for(int i=0;fa[u][i];i++)fa[u][i+1]=fa[fa[u][i]][i]; dfn[u]=++df;vector <data> :: iterator it; for(it=v[u].begin();it!=v[u].end();++it)dep[it->v]=dep[u]+1,fa[it->v][0]=u,dfs(it->v); } inline void pre(){for(int i=1;i<=k;i++)sort(v[i].begin(),v[i].end());dfs(1);} inline int lca(int u,int v)//倍增lca { if(dep[u]<dep[v])swap(u,v); for(int d=dep[u]-dep[v],i=0;d;d>>=1,i++)if(d&1)u=fa[u][i];if(u==v)return u; for(int i=17;i>=0;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];return fa[u][0]; } inline void clear() { for(int i=1;i<=k;i++)v[i].clear(); for(int i=1;i<=k;i++)for(int j=0;j<18;j++)fa[i][j]=0;df=0; } } namespace Grph { const int N=5*1e4+10;const int V=4*N;const int E=20*N; int tp[V];int ctt;vector <int> eif[N];vector <int> eof[N];vector <int> eib[N];vector <int> eob[N]; vector <int> tr;int v[E];int x[E];int ct;int al[V];int val[E];int s; inline bool cmp(int a,int b){return dfn[tp[a]]<dfn[tp[b]];} inline void add(int u,int V,int w){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=w;} inline void ins(int u,int V,int w,int d)//插入一个边 { if(u==1)add(s,ctt+1,0),add(s,ctt+3,0);for(int i=1;i<=4;i++)tp[ctt+i]=d;//拆成4条边 add(ctt+1,ctt+2,w);add(ctt+1,ctt+4,w);add(ctt+3,ctt+4,w);add(ctt+3,ctt+2,w); eof[u].push_back(++ctt);eif[V].push_back(++ctt);eob[u].push_back(++ctt);eib[V].push_back(++ctt); } inline void build() { for(int u=1;u<=n;u++) { sort(eof[u].begin(),eof[u].end(),cmp);sort(eif[u].begin(),eif[u].end(),cmp); sort(eob[u].begin(),eob[u].end(),cmp);sort(eib[u].begin(),eib[u].end(),cmp); for(int i=0;i<(int)eof[u].size()-1;i++)add(eof[u][i],eof[u][i+1],0);//将长链连出来 for(int i=0;i<(int)eif[u].size()-1;i++)add(eif[u][i],eif[u][i+1],0); for(int i=0;i<(int)eob[u].size()-1;i++)add(eob[u][i+1],eob[u][i],0); for(int i=0;i<(int)eib[u].size()-1;i++)add(eib[u][i+1],eib[u][i],0); tr.resize(eof[u].size()+eif[u].size()); merge(eif[u].begin(),eif[u].end(),eof[u].begin(),eof[u].end(),tr.begin(),cmp); for(int t=0,i=0,j=0;t<(int)tr.size()-1;t++)//然后两两求lca连边 { if(tr[t]&1)j++;else i++;int w=dep[Tree::lca(tp[tr[t]],tp[tr[t+1]])]; if(i!=0&&j!=(int)eof[u].size())add(eif[u][i-1],eof[u][j],w); if(i!=(int)eib[u].size()&&j!=0)add(eib[u][i],eob[u][j-1],w); } } } struct data{int u;ll d;friend bool operator <(data a,data b){return a.d>b.d;}}; ll d[V];bool book[V];priority_queue <data> pq; inline void solve()//跑dijkstra { for(int i=1;i<=ctt;i++)d[i]=(1LL<<40);d[s]=0; for(pq.push((data){s,0});!pq.empty();) { data nw=pq.top();pq.pop();if(book[nw.u])continue;book[nw.u]=true; for(int i=al[nw.u];i;i=x[i]) if(!book[v[i]]&&d[v[i]]>nw.d+val[i])d[v[i]]=nw.d+val[i],pq.push((data){v[i],d[v[i]]}); } for(int i=2;i<=n;i++) { ll ret=(1LL<<40);for(int j=0;j<(int)eif[i].size();j++)ret=min(ret,d[eif[i][j]]); for(int j=0;j<(int)eib[i].size();j++)ret=min(ret,d[eib[i][j]]);printf("%lld\n",ret); } } inline void clear() { for(int i=1;i<=n;i++)eif[i].clear(); for(int i=1;i<=n;i++)eof[i].clear(); for(int i=1;i<=n;i++)eib[i].clear(); for(int i=1;i<=n;i++)eob[i].clear(); for(int i=1;i<=ctt+1;i++)al[i]=0; for(int i=1;i<=ctt+1;i++)book[i]=false;ct=0;ctt=0; } } inline void solve() { scanf("%d%d%d",&n,&m,&k);Grph::s=4*m+1; for(int i=1,u,v,w,d;i<=m;i++)scanf("%d%d%d%d",&u,&v,&w,&d),Grph::ins(u,v,w,d); for(int i=1,u,v,w;i<k;i++)scanf("%d%d%d",&u,&v,&w),Tree::add(u,v,w); Tree::pre();Grph::build();Grph::solve(); } inline void clear(){Tree::clear();Grph::clear();} int main(){scanf("%d",&T);for(int z=1;z<=T;z++)solve(),clear();return 0;}//拜拜程序~ ```