LS 22 Longest path on DAG的最短路SPFA算法如何改写为长尾词？

本文共计497个文字，预计阅读时间需要2分钟。

输入：n个顶点，m条边，表示顶点数和边数。接下来的m行包含两个整数ai, bi，表示边ai→bi。（1≤n≤105，1≤m≤106，1≤ai, bi≤n）

输出：l，表示最长路径的长度。l=1+Sample

Longest path on DAG

G.

Input

n,m, which denote the number of vertices and edges.

mlines contains two integerai,bi, which denote edgeai→bi.

(1≤n≤105,1≤m≤106,1≤ai<bi≤n)

Ouptut

l, which denotes the length of longest path.

l+1

Sample input

4 41 21 32 43 4

Sample output

21 2 4

思路：建边，建个源点0和汇点，然后依次在源点和汇点与中间所有点连边。求源点和汇点的最长路就是答案。

本题需要从汇点往源点做最短路

#include<iostream>#include<cstring>using namespace std;const int mm=6e6+9;int ver[mm],next[mm],head[mm],edge,q[mm],dis[mm],fa[mm];bool vis[mm];int n,m;void prepare(){ for(int i=0;i<n+2;i++)head[i]=-1,fa[i]=-1;edge=0;}void add(int aa,int bb){ ver[edge]=bb;next[edge]=head[aa];head[aa]=edge++;}int spfa(){ memset(dis,-1,sizeof(dis)); memset(vis,0,sizeof(vis)); int l=0,r=1,u,v; q[l]=0;vis[0]=1;dis[0]=0; while(l^r) {u=q[l++];l%=mm;vis[u]=0; for(int i=head[u];i!=-1;i=next[i]) { v=ver[i]; if(dis[v]<dis[u]+1) { dis[v]=dis[u]+1;fa[v]=u; if(!vis[v]) q[r++]=v,r%=mm,vis[v]=1; } else if(dis[v]==dis[u]+1&&fa[v]>u)fa[v]=u; } } cout<<dis[n+1]-2<<"\n"; int pos=0,zz=fa[n+1]; while(zz!=-1) { ver[pos++]=zz; zz=fa[zz]; } for(int i=0;i<pos-2;i++) cout<<ver[i]<<" "; cout<<ver[pos-2]<<"\n";}int main(){ while(cin>>n>>m) { int a,b; prepare(); for(int i=0;i<m;i++) { cin>>a>>b;add(b,a);///建反向边 } for(int i=1;i<=n;i++) add(0,i),add(i,n+1); spfa(); }}