题解 P9981 [USACO23DEC] Minimum Longest Trip G
cjh20090318
·
·
题解
题意
求每一条路径的长度和边权和。
## 分析
最长的路径很好求，在 DAG 上拓扑排序后动态规划即可。（具体的实现可以参考 [OI-Wiki](https://oi-wiki.org/graph/dag/#dp-%E6%B1%82%E6%9C%80%E9%95%BF%E7%9F%AD%E8%B7%AF)）
现在的问题就变成了怎么求字典序最小。
如果朴素的进行比较判断时间复杂度在最坏情况下是 $O(N^2)$，难以通过此题，考虑优化。
> 一个序列比等长的另一个序列字典序更小，当且仅当在它们不同的第一个位置，前者比后者的元素更小。
说明序列的字典序只和其中一个数有关，于是需要一个更快的方法，来找到第一个不同的位置。
类似于字符串哈希的方法，可以预处理前缀哈希使得单次查询一个子串的复杂度变成 $O(1)$。但是因为没有记录一条链上的所有节点所以不便于二分，考虑换成倍增。
然后是类似于最近公共祖先的倍增写法，不断的向上跳找到第一个标签值不同的位置，然后比较即可。
时间复杂度 $O(M \log N)$，可以通过此题。
## 代码
```cpp
//the code is from chenjh
#include<cstdio>
#include<queue>
#include<utility>
#include<vector>
#define MAXN 200002
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const unsigned int p=131;//自然溢出哈希底数。
int n,m,in[MAXN];
int tp[MAXN],c=0;
vector<PII> G[MAXN];
int f[MAXN];//最长链的长度。
LL s[MAXN];//标签和。
int fa[MAXN][19];//链上节点倍增。
ULL pn[MAXN<<2],hs[MAXN][19];//倍增哈希。
int main(){
pn[0]=1;
for(int i=1,mi=MAXN<<2;i<mi;i++) pn[i]=pn[i-1]*p;//预处理哈希底数的幂次。
scanf("%d%d",&n,&m);
for(int i=0,u,v,w;i<m;i++)
scanf("%d%d%d",&u,&v,&w),
G[u].emplace_back(v,w),++in[v];
queue<int> Q;
for(int i=1;i<=n;i++)if(!in[i]) Q.push(i);
for(int u;!Q.empty();){//对图进行拓扑排序。
u=Q.front(),Q.pop();
tp[++c]=u;
for(const auto&[v,w]:G[u])if(!--in[v]) Q.push(v);
}
for(int i=n,u;i>0;--i){//根据拓扑序倒推。
u=tp[i];
for(const auto&[v,w]:G[u])
if(f[u]<f[v]+1||(f[u]==f[v]+1&&(ULL)w<*hs[u]))//存在更长的路径或长度相同但当前标签比答案更小就直接更新答案。
f[u]=f[v]+1,s[u]=s[v]+w,*fa[u]=v,*hs[u]=w;
else if(f[u]==f[v]+1&&(ULL)w==*hs[u]){//长度相同且第一位也相同，才有必要进行进一步的判断。
int x=*fa[u],y=v;
for(int k=18;k>=0;--k)if(fa[x][k] && fa[y][k] && hs[x][k]==hs[y][k])
x=fa[x][k],y=fa[y][k];//向上跳找到第一个不同的点。
if(x&&y&&*hs[y]<*hs[x])
f[u]=f[v]+1,s[u]=s[v]+w,*fa[u]=v,*hs[u]=w;//不同的位置更小，更新答案。
}
for(int k=1;k<19;k++)
fa[u][k]=fa[fa[u][k-1]][k-1],
hs[u][k]=hs[fa[u][k-1]][k-1]*pn[1<<(k-1)]+hs[u][k-1];//倍增处理祖先和祖先的哈希。
}
for(int i=1;i<=n;i++) printf("%d %lld\n",f[i],s[i]);
return 0;
}
```