nowcoder 提高组模拟赛 最长路 解题报告

最长路

链接:

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

上一篇:[CQOI2009] 叶子的颜色 解题报告(树形DP)


下一篇:C#版(击败100.00%的提交) - Leetcode 744. 寻找比目标字母大的最小字母 - 题解