bzoj 4016: [FJOI]最短路径树问题

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;}

如果觉得《bzoj 4016: [FJOI]最短路径树问题》对你有帮助，请点赞、收藏，并留下你的观点哦！