昆明网站建设高端定制,wordpress建站课程,网站维护多少钱一个月,智联招聘网站多少钱做的题目描述 给一个包含 nn 个点#xff0c;mm 条边的无向连通图。从顶点 11出发#xff0c;往其余所有点分别走一次并返回。
往某一个点走时#xff0c;选择总长度最短的路径走。若有多条长度最短的路径#xff0c;则选择经过的顶点序列字典序最小的那条路径#xff08;如路…题目描述 给一个包含 nn 个点mm 条边的无向连通图。从顶点 11出发往其余所有点分别走一次并返回。
往某一个点走时选择总长度最短的路径走。若有多条长度最短的路径则选择经过的顶点序列字典序最小的那条路径如路径 AA 为 1,32,111,32,11路径 BB 为 1,3,2,111,3,2,11路径 BB 字典序较小。注意是序列的字典序的最小而非路径中节点编号相连的字符串字典序最小。到达该点后按原路返回然后往其他点走直到所有点都走过。
可以知道经过的边会构成一棵最短路径树。请问在这棵最短路径树上最长的包含 kk 个点的简单路径长度为多长长度为该最长长度的不同路径有多少条
这里的简单路径是指对于一个点最多只经过一次的路径。不同路径是指路径两端端点至少有一个不同点 AA 到点 BB 的路径和点 BB 到点 AA 视为同一条路径。
输入格式 第一行输入三个正整数 n,m,kn,m,k表示有 nn 个点 mm 条边要求的路径需要经过 kk 个点。 接下来输入 mm 行每行三个正整数 A_i,B_i,C_iA i ,B i ,C i 1\leq A_i,B_i\leq n,1\leq C_i\leq 100001≤A i ,B i ≤n,1≤C i ≤10000表示 A_iA i 和 B_iB i 间有一条长度为 C_iC i 的边。数据保证输入的是连通的无向图。
输出格式 输出一行两个整数以一个空格隔开第一个整数表示包含 kk 个点的路径最长为多长第二个整数表示这样的不同的最长路径有多少条。
输入数据 1 6 6 4 1 2 1 2 3 1 3 4 1 2 5 1 3 6 1 5 6 1 输出数据 1 3 4 数据范围与提示 对于所有数据n\leq 30000,m\leq 60000n≤30000,m≤600002\leq k\leq n2≤k≤n。
数据保证最短路径树上至少存在一条长度为 kk 的路径。
变更记录 因本题原题与P0087合并果子重复
本题更换为[FJOI2014] 最短路径树问题
#include cstdio
#include cstring
#include algorithm
#include vector
#include queue
const int N3e410;
struct Edge
{int v,w;bool friend operator (Edge n1,Edge n2){return n1.vn2.v;}
}t;
std::vector Edge e[N],e0[N];
int n,m,k;
const int inf0x3f3f3f3f;
#define P std::pair int,int
std::priority_queue P,std::vector P ,std::greater P q;
int dis[N],used[N];
int head[N],to[N1],edge[N1],Next[N1],cnt;
void add(int u,int v,int w)
{to[cnt]v,Next[cnt]head[u],edge[cnt]w,head[u]cnt;
}
void disj()
{memset(dis,0x3f,sizeof(dis));q.push(std::make_pair(dis[1]0,1));while(!q.empty()){int uq.top().second;q.pop();if(used[u]) continue;used[u]1;for(int i0;ie[u].size();i){int ve[u][i].v,we[u][i].w;if(dis[v]dis[u]w){dis[v]dis[u]w;q.push(std::make_pair(dis[v],v));}}}memset(used,0,sizeof(used));
}
void dfsbuild(int now)
{used[now]1;for(int i0;ie0[now].size();i){int ve0[now][i].v,we0[now][i].w;if(!used[v]){add(now,v,w);add(v,now,w);dfsbuild(v);}}
}
void build()
{for(int u1;un;u){for(int i0;ie[u].size();i){int ve[u][i].v,we[u][i].w;if(dis[v]dis[u]w)t{v,w},e0[u].push_back(t);}std::sort(e0[u].begin(),e0[u].end());}dfsbuild(1);
}
int ans,siz[N],rt,mi,mxlen[N],mx,del[N],td[N],tmxlen[N],scnt[N],tcnt[N];
int max(int x,int y){return xy?x:y;}
void dfsroot(int now,int fa,int sz)
{siz[now]1;int mx00;for(int ihead[now];i;iNext[i]){int vto[i];if(vfa||del[v]) continue;dfsroot(v,now,sz);mx0max(mx0,siz[v]);siz[now]siz[v];}mx0max(mx0,sz-siz[now]);if(mx0mi) mimx0,rtnow;
}
void dfs(int now,int fa,int dis,int dep)
{if(depk) return;if(mxdismxlen[k-dep]){mxdismxlen[k-dep];ansscnt[k-dep];}else if(mxdismxlen[k-dep])ansscnt[k-dep];for(int ihead[now];i;iNext[i]){int vto[i];if(vfa||del[v]) continue;dfs(v,now,disedge[i],dep1);}if(tmxlen[dep]dis){tmxlen[dep]dis;tcnt[dep]1;}else if(tmxlen[dep]dis)tcnt[dep];
}
void dfz(int now,int sz)
{mi130;dfsroot(now,0,sz);nowrt;del[now]1;for(int ihead[now];i;iNext[i]){int vto[i];if(del[v]) continue;dfs(v,now,edge[i],1);for(int j1;tmxlen[j]!-inf;j){if(tmxlen[j]mxlen[j]){scnt[j]tcnt[j];mxlen[j]tmxlen[j];}else if(tmxlen[j]mxlen[j])scnt[j]tcnt[j];tcnt[j]0,tmxlen[j]-inf;}}if(mxmxlen[k]) ansscnt[k],mxmxlen[k];else if(mxmxlen[k]) ansscnt[k];for(int i1;mxlen[i]!-inf;i) mxlen[i]-inf;for(int ihead[now];i;iNext[i])if(!del[to[i]])dfz(to[i],siz[to[i]]);
}
int main()
{//freopen(data.in,r,stdin);//freopen(wr.out,w,stdout);scanf(%d%d%d,n,m,k);for(int u,v,w,i1;im;i){scanf(%d%d%d,u,v,w);t{v,w};e[u].push_back(t);t{u,w};e[v].push_back(t);}disj();build();--k;for(int i0;ik1;i)tmxlen[i]mxlen[i]-inf;dfz(1,n);printf(%d %d\n,mx,ans);return 0;
}
