Description
給一個包含n個點，m條邊的無向連通圖。從頂點1出發，往其余所有點分別走一次并返回。
往某一個點走時，選擇總長度最短的路徑走。若有多條長度最短的路徑，則選擇經過的頂點序列字典序最小的那條路徑(如路徑A為1,32,11，路徑B為1,3,2,11，路徑B字典序較小。注意是序列的字典序的最小，而非路徑中節點編號相連的字符串字典序最小)。到達該點后按原路返回，然后往其他點走，直到所有點都走過。
可以知道，經過的邊會構成一棵最短路徑樹。請問，在這棵最短路徑樹上，最長的包含K個點的簡單路徑長度為多長？長度為該最長長度的不同路徑有多少條？
這里的簡單路徑是指：對于一個點最多只經過一次的路徑。不同路徑是指路徑兩端端點至少有一個不同，點A到點B的路徑和點B到點A視為同一條路徑。
solution
正解：點分治
構出最短路圖，在最短路圖上面盡量走編號小的點，直到所有的點都加入集合中，構成了最短路樹
然后點分治即可
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
#include <vector>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=30005,inf=2e8;
int n,m,k,Head[N],nxt[N*10],to[N*10],dis[N*10],num=1,head[N];
inline void link1(int x,int y,int z){nxt[++num]=Head[x];to[num]=y;dis[num]=z;Head[x]=num;}
inline void link2(int x,int y,int z){nxt[++num]=head[x];to[num]=y;dis[num]=z;head[x]=num;}
bool v[N],d[N];int dd[N];
inline void spfa(int S){queue<int>q;while(!q.empty())q.pop();for(RG int i=0;i<=n;i++)dd[i]=inf,v[i]=0;q.push(S);dd[S]=0;v[S]=1;int x,u;while(!q.empty()){x=q.front();q.pop();for(RG int i=Head[x];i;i=nxt[i]){u=to[i];if(dd[x]+dis[i]<dd[u]){dd[u]=dd[x]+dis[i];if(!v[u])v[u]=1,q.push(u);}}v[x]=0;}
}
struct Grath{int x,dis,id;bool operator <(const Grath &pr)const{return x<pr.x;}};
vector<Grath>G[N];
struct edge{int x,y,z;}e[N*10];
int root=0,son[N]={N},sz[N],sum;bool vis[N];
inline void getroot(int x,int last){sz[x]=1;son[x]=0;for(int i=head[x];i;i=nxt[i]){int u=to[i];if(vis[u] || u==last)continue;getroot(u,x);sz[x]+=sz[u];if(sz[u]>son[x])son[x]=sz[u];}son[x]=Max(son[x],sum-sz[x]);if(son[x]<son[root])root=x;
}
int g[N],f[N],de[N],den=0;bool inde[N];
inline void upd(int x,int last,int dist,int l){if(l>k)return ;if(dist>f[l]){f[l]=dist,g[l]=1;if(!inde[l])inde[l]=true,de[++den]=l;}else if(dist==f[l])g[l]++;for(int i=head[x];i;i=nxt[i]){int u=to[i];if(vis[u] || u==last)continue;upd(u,x,dist+dis[i],l+1);}
}
int ans=0,cnt=0;
inline void getdis(int x,int last,int dist,int l){if(l>k)return ;if(dist+f[k-l]>ans)ans=dist+f[k-l],cnt=g[k-l];else if(dist+f[k-l]==ans)cnt+=g[k-l];for(int i=head[x];i;i=nxt[i]){int u=to[i];if(vis[u] || u==last)continue;getdis(u,x,dist+dis[i],l+1);}
}
inline void calc(int x){g[0]=1;for(int i=head[x];i;i=nxt[i]){int u=to[i];if(vis[u])continue;getdis(u,x,dis[i],2);upd(u,x,dis[i],1);}while(den)f[de[den]]=0,g[de[den]]=0,inde[de[den]]=0,den--;
}
inline void solve(int x){vis[x]=1;calc(x);for(int i=head[x];i;i=nxt[i]){int u=to[i];if(vis[u])continue;root=0;sum=sz[u];getroot(u,x);solve(root);}
}
bool b[N];
inline void dfs(int x){b[x]=1;for(RG int i=0,sz=G[x].size();i<sz;i++){int u=G[x][i].x,id=G[x][i].id;if(dd[x]+G[x][i].dis==dd[u] && !b[u]){link2(e[id].x,e[id].y,e[id].z);link2(e[id].y,e[id].x,e[id].z);dfs(u);}}
}
void work()
{int x,y,z;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);e[i].x=x;e[i].y=y;e[i].z=z;link1(x,y,z);link1(y,x,z);G[x].push_back((Grath){y,z,i});G[y].push_back((Grath){x,z,i});}for(int i=1;i<=n;i++)sort(G[i].begin(),G[i].end());spfa(1);dfs(1);sum=n;root=0;getroot(1,1);solve(root);printf("%d %d\n",ans,cnt);
}int main()
{work();return 0;
}
轉載于:https://www.cnblogs.com/Yuzao/p/8046737.html
總結
以上是生活随笔為你收集整理的bzoj 4016: [FJOI2014]最短路径树问题的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
