最长路
链接：
https://www.nowcoder.com/acm/contest/178/A
来源：牛客网
题目描述
有一张 \(n\) 个点 \(m\) 条边的有向图，每条边上都带有一个字符，字符用一个数字表示。
求以每个点为起点的最长路，输出走过的边的字符构成的字符串的字典序最小的方案。
为了方便，你需要这样输出方案：
如果最长路无限长，则输出Infinity
否则假设方案走过的边的字符依次为 \(w_1,w_2,\cdots,w_k\) ，输出\((\sum\limits_{i=1}^kw_i\times29^i) \bmod 998244353\)
输入描述:
第一行两个整数 \(n\),\(m\) ，表示有向图的结点个数和边数。
接下来 \(m\) 行，每行三个整数 \(x,y,w\) ，表示有一条从 \(x\) 连向 \(y\) 的边，上面有字符 \(w\) 。
输出描述:
共 \(n\) 行，第 \(i\) 行表示第 \(i\) 个点所求的方案，输出方式见题目描述。
备注:
全部的输入数据满足：
- \(1 ≤ n ≤ 1000000\)
- \(1 ≤ m ≤ 1000000\)
- \(0 ≤ \text{字符} ≤ 10^9\)
各个测试点的性质如下：(若为空，则表示没有特殊性质)
| 测试点标号 | n | m | 特殊性质 |
|---|---|---|---|
| \(1,2,3,4\) | \(\le 1000\) | \(\le 1000\) | |
| \(5,6\) | 所有字符=0 | ||
| \(7,8\) | 所有字符相等 | ||
| \(9,10,11,12,13,14,15,16\) | 所有字符互不相等 | ||
| \(17,18\) | \(\le 200000\) | \(\le 200000\) | |
| \(19,20\) |
如果脑子傻了先缩个点就爆0了。。有向图有自环时直接tarjan出不来的哦~
直接反向\(topo\)排序进不去就可以判有没有经过环了。
如果没有字典序的要求显然就是一个最长路的简单题。
考虑如何使字典序最小，题解给出了两个做法，我就两个都写了写。
方法\(1\)，在最短路树上维护倍增数组。
我们发现，简单的判断字典序是没法判断一个正在转移别人的点之前的路径的，如果连出去的边和连出去的点之前的转移值的那条边相等，我们就没得办法了。
为了可以判断，我们对路径的值维护一个\(hash\)值，来判断两条路径是否相等，通过倍增找到路径不相等的地方并进行比较。
复杂度\(O(nlogn)\)
Code：
#include <cstdio>
#define ll long long
const int N=1e6+10;
const ll mod=998244353ll;
int head[N],to[N],edge[N],Next[N],cnt;
void add(int u,int v,int w)
{
to[++cnt]=v,edge[cnt]=w,Next[cnt]=head[u],head[u]=cnt;
}
ll po[N];
int n,m,in[N],f[N][21],pre[N],q[N],l=1,r=0;
ll g[N][21];
struct node
{
int u,las,len;ll ans;
bool friend operator <(node n1,node n2)
{
if(n1.len!=n2.len||n1.las!=n2.las) return n1.len==n2.len?n1.las>n2.las:n1.len<n2.len;
int u1=n1.u,u2=n2.u;
for(int i=20;~i;i--)
if(f[u1][i]&&g[u1][i]==g[u2][i])
u1=f[u1][i],u2=f[u2][i];
return pre[u1]>pre[u2];
}
}dp[N],t;
node max(node n1,node n2){return n1<n2?n2:n1;}
int main()
{
scanf("%d%d",&n,&m);
po[0]=1;
for(int i=1;i<=n;i++) po[i]=po[i-1]*29ll%mod;
for(int u,v,w,i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(v,u,w),in[u]++;
}
for(int i=1;i<=n;i++)
if(!in[i]) q[++r]=i;
while(l<=r)
{
int now=q[l++];
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
in[v]--;
t={now,edge[i],dp[now].len+1,(dp[now].ans+edge[i])*29ll%mod};
dp[v]=max(dp[v],t);
if(!in[v])
{
f[v][0]=dp[v].u;
g[v][0]=dp[v].las;
pre[v]=dp[v].las;
for(int k=1;f[v][k-1];k++)
{
f[v][k]=f[f[v][k-1]][k-1];
g[v][k]=(g[f[v][k-1]][k-1]*po[1<<k-1]+g[v][k-1])%mod;
}
q[++r]=v;
}
}
}
for(int i=1;i<=n;i++)
{
if(in[i]) puts("Infinity");
else printf("%lld\n",dp[i].ans);
}
return 0;
}
方法\(2\)，根据最长路的长度把点分层。
这个方法更加巧妙，常数也更小。
先把最长路求出来，然后对每个点安排它的层数，排除了一些无用边。
那么同层的点就可以按照路径字典序来判断这个点之前的路径了。
具体的，对这层向下层的点连的边排序，以边的权值为第一关键字，以上层的点的字典序为第二关键字就行了。
Code:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ll long long
const ll mod=998244353ll;
const int N=1e6+10;
int dis[N],edge[N],head[N],to[N],Next[N],cnt;
void add(int u,int v,int w)
{
to[++cnt]=v,edge[cnt]=w,Next[cnt]=head[u],head[u]=cnt;
}
int q[N],l=1,r=0,n,m,mx,in[N],pre[N];
ll ans[N];
using std::vector;
int max(int x,int y){return x>y?x:y;}
vector <int> pot[N];
struct node
{
int u,v,w,pre;
bool friend operator <(node n1,node n2)
{
return n1.w==n2.w?n1.pre<n2.pre:n1.w<n2.w;
}
}e[N];
int main()
{
scanf("%d%d",&n,&m);
for(int u,v,w,i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(v,u,w),++in[u];
}
memset(dis,-1,sizeof(dis));
for(int i=1;i<=n;i++)
if(!in[i])
q[++r]=i,dis[i]=0;
while(l<=r)
{
int now=q[l++];
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
--in[v];
dis[v]=max(dis[v],dis[now]+1);
mx=max(dis[v],mx);
if(!in[v]) q[++r]=v;
}
}
for(int i=1;i<=n;i++)
if(~dis[i]) pot[dis[i]].push_back(i);
int d=0;
do
{
int tot=0,tot0=0;
for(int i=0;i<pot[d].size();i++)
for(int j=head[pot[d][i]];j;j=Next[j])
if(dis[to[j]]==d+1)
e[++tot]={pot[d][i],to[j],edge[j],pre[pot[d][i]]};
std::sort(e+1,e+1+tot);
for(int i=1;i<=tot;i++)
if(!pre[e[i].v])
{
pre[e[i].v]=++tot0;
ans[e[i].v]=(ans[e[i].u]+e[i].w)*29ll%mod;
}
d++;
}while(d<mx);
for(int i=1;i<=n;i++)
{
if(in[i]) puts("Infinity");
else printf("%lld\n",ans[i]);
}
return 0;
}
2018.10.21