4016: [FJOI2014] 最短路径树问题
Time Limit: 5 Sec Memory Limit: 512 MBSubmit: 1715 Solved: 596
[ Submit ][ Status ][ Discuss ]
Description
给一个包含 n 个点,m 条边的无向连通图。从顶点 1 出发,往其余所有点分别走一次并返回。
往某一个点走时,选择总长度最短的路径走。若有多条长度最短的路径,则选择经过的顶点序列字典序最小的那条路径 (如路径 A 为 1,32,11,路径 B 为 1,3,2,11,路径 B 字典序较小。注意是序列的字典序的最小,而非路径中节点编号相连的字符串字典序最小)。到达该点后按原路返回,然后往其他点走,直到所有点都走过。
可以知道,经过的边会构成一棵最短路径树。请问,在这棵最短路径树上,最长的包含 K 个点的简单路径长度为多长?长度为该最长长度的不同路径有多少条?
这里的简单路径是指:对于一个点最多只经过一次的路径。不同路径是指路径两端端点至少有一个不同,点 A 到点 B 的路径和点 B 到点 A 视为同一条路径。
Input
第一行输入三个正整数 n,m,K,表示有 n 个点 m 条边,要求的路径需要经过 K 个点。接下来输入 m 行,每行三个正整数 Ai,Bi,Ci(1<=Ai,Bi<=n,1<=Ci<=10000),表示 Ai 和 Bi 间有一条长度为 Ci 的边。数据保证输入的是连通的无向图。
Output
输出一行两个整数,以一个空格隔开,第一个整数表示包含 K 个点的路径最长为多长,第二个整数表示这样的不同的最长路径有多少条。
Sample Input
6 6 4
1 2 1
2 3 1
3 4 1
2 5 1
3 6 1
5 6 1
1 2 1
2 3 1
3 4 1
2 5 1
3 6 1
5 6 1
Sample Output
3 4
HINT
对于所有数据 n<=30000,m<=60000,2<=K<=n。数据保证最短路径树上至少存在一条长度为 K 的路径。2016.12.7 新加数据一组 by - wyx-150137
思路 {
显然构完树后直接点分治就可以了。
构树的话我考场上直接暴力记录路径 + 暴力修改决策 (因为树高期望 $log$....)。
本地 AC,BZOJMLE 一次是什么鬼。。。。
}
- #include<bits/stdc++.h>
- #define RG register
- #define il inline
- #define ll long long
- #define db double
- #define inf 1000000000
- #define N 30010
- using namespace std;
- struct ed{int nxt,to,c;}E[N*4],e[N*2];
- int HEAD[N],TOT,head[N],tot;
- void LINK(int u,int v,int c){
- E[TOT].nxt=HEAD[u];E[TOT].to=v;
- E[TOT].c=c;HEAD[u]=TOT++;
- }
- void link(int u,int v,int c){
- e[tot].nxt=head[u];e[tot].to=v;
- e[tot].c=c;head[u]=tot++;
- }
- int n,m,D[N];
- typedef pair<int,int>pir;
- pair<int,int>pre[N];
- bool in[N];
- queue<int>que;
- vector<pir>ee[N];
- bool V[N];
- void DFS(int u,int faa){
- V[u]=1;
- for(int i=HEAD[u];i!=-1;i=E[i].nxt){
- int v=E[i].to;if(V[v]||v==faa)continue;
- if(D[v]==D[u]+E[i].c){
- link(v,u,E[i].c),link(u,v,E[i].c),DFS(v,u);
- }
- }
- }
- void spfa(){
- que.push(1);
- for(int i=1;i<=n;++i)D[i]=300000001;
- D[1]=0;
- while(!que.empty()){
- int u=que.front();que.pop();in[u]=0;
- for(int i=HEAD[u];i!=-1;i=E[i].nxt){
- int v=E[i].to;
- if(D[v]>D[u]+E[i].c){
- D[v]=D[u]+E[i].c;
- pre[v]=make_pair(u,E[i].c);
- if(!in[v])que.push(v),in[v]=1;
- }
- }
- }
- DFS(1,1);
- }
- int f[N],sum,rt,k,sz[N],ans,ans2;bool vis[N];
- int tong[N],temp[N];
- int sumtong[N],sumtemp[N];
- void getrt(int u,int faa){
- f[u]=0,sz[u]=1;
- for(int i=head[u];i!=-1;i=e[i].nxt){
- int v=e[i].to;if(v==faa||vis[v])continue;
- getrt(v,u);f[u]=max(f[u],sz[v]);
- sz[u]+=sz[v];
- }f[u]=max(f[u],sum-sz[u]);
- if(f[u]<f[rt])rt=u;
- }
- void dfs(int u,int faa,int dep,int d){
- if(dep>k)return;
- if(temp[dep]<d)temp[dep]=d,sumtemp[dep]=1;
- else if(temp[dep]==d)sumtemp[dep]++;
- if(tong[k+1-dep]!=-1){
- if(ans==temp[dep]+tong[k+1-dep]&&d==temp[dep])ans2+=sumtong[k+1-dep];
- else if(ans<temp[dep]+tong[k+1-dep]&&d==temp[dep])ans2=sumtong[k+1-dep]*sumtemp[dep];
- ans=max(temp[dep]+tong[k+1-dep],ans);
- }
- for(int i=head[u];i!=-1;i=e[i].nxt){
- int v=e[i].to;if(v==faa||vis[v])continue;
- dfs(v,u,dep+1,d+e[i].c);
- }
- }
- void modify(int u,int faa,int dep){
- if(dep>k)return;
- if(tong[dep]<temp[dep])sumtong[dep]=sumtemp[dep];
- else if(tong[dep]==temp[dep])sumtong[dep]+=sumtemp[dep];
- tong[dep]=max(tong[dep],temp[dep]),temp[dep]=sumtemp[dep]=0;
- for(int i=head[u];i!=-1;i=e[i].nxt){
- int v=e[i].to;if(v==faa||vis[v])continue;
- modify(v,u,dep+1);
- }
- }
- void solve(int u){
- vis[u]=1;
- for(int i=2;i<=k+k;++i)tong[i]=temp[i]=-1,sumtemp[i]=sumtong[i]=0;
- tong[1]=0,sumtong[1]=1;
- for(int i=head[u];i!=-1;i=e[i].nxt){
- int v=e[i].to;if(vis[v])continue;
- dfs(v,u,2,e[i].c);
- modify(v,u,2);
- }
- for(int i=head[u];i!=-1;i=e[i].nxt){
- int v=e[i].to;if(vis[v])continue;
- sum=sz[v],rt=0;
- getrt(v,v);
- solve(rt);
- }
- }
- int main(){
- scanf("%d%d%d",&n,&m,&k);
- memset(head,-1,sizeof(head));
- memset(HEAD,-1,sizeof(HEAD));
- for(int i=1;i<=m;++i){
- int u,v,c;scanf("%d%d%d",&u,&v,&c);
- ee[u].push_back(make_pair(v,c));
- ee[v].push_back(make_pair(u,c));
- }
- for(int i=1;i<=n;++i){
- sort(ee[i].begin(),ee[i].end());
- for(int j=ee[i].size()-1;j!=-1;j--)
- LINK(i,ee[i][j].first,ee[i][j].second);
- }
- spfa();
- f[0]=n+1,sum=n;
- getrt(1,1);
- solve(rt);
- printf("%d %d\n",ans,ans2);
- return 0;
- }