bzoj4016(点分治)

Posted on   |   In

题解:

强行凑题…..

前面构造最短路树 然后后半部分模板点分统计贡献

这个最短路树要保证路径的字典序最小 那么我们可以跑出最短路 枚举边 看距离差值是否等于边权 然后连边 对于所有连边排序以后 做$dfs$建树

第二部分就直接考虑子树合并 维护每个深度下的最大距离 以及方案数 枚举统计贡献

复杂度 $O(mlogn+nlogn)$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=1e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
const ll inf=1e12;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m,k;



vector<pii>vec[MAXN];
ll dis[MAXN],ans1;
ll ans2;
bool vis[MAXN];
typedef struct Node{
    int x,y,z;
}Node;
Node Edge[MAXN];

typedef struct node{
    int v;ll d;
    friend bool operator<(node aa,node bb){
	return aa.d>bb.d;
    }
}node;
priority_queue<node>que;

void dij(int s){
    inc(i,1,n)vis[i]=0,dis[i]=inf;
    dis[s]=0;que.push((node){s,0});
    while(!que.empty()){
	node t=que.top();que.pop();
	if(vis[t.v])continue;
	vis[t.v]=1;
	link(t.v){
	    if(dis[j->t]>dis[t.v]+j->v){
		dis[j->t]=dis[t.v]+j->v;
		que.push((node){j->t,dis[j->t]});
	    }
	}
    }
    for(int i=1;i<=m;i++){
	int x=Edge[i].x;int y=Edge[i].y;
	if(dis[x]>dis[y])swap(x,y);
	if(Edge[i].z==dis[y]-dis[x])vec[x].pb(mp(y,Edge[i].z));
    }
}

void dfs(int x){
    vis[x]=1;
    for(int i=0;i<vec[x].size();i++){
	if(vis[vec[x][i].first])continue;
	add(x,vec[x][i].first,vec[x][i].second);
	add(vec[x][i].first,x,vec[x][i].second);
	dfs(vec[x][i].first);
    }
}

int rt,sz[MAXN],maxx[MAXN],base;
int key;
void get_root(int x,int pre){
    sz[x]=1;maxx[x]=0;
    link(x){
	if(vis[j->t]||j->t==pre)continue;
	get_root(j->t,x);
	sz[x]+=sz[j->t];maxx[x]=max(maxx[x],sz[j->t]);
    }
    maxx[x]=max(maxx[x],base-sz[x]);
    if(key>maxx[x])rt=x,key=maxx[x];
}
int c1[MAXN];
ll MAxx[MAXN];
int num[MAXN];
int st[MAXN],St[MAXN],tot,tot1;
void _dfs(int x,int pre){
    num[x]=num[pre]+1;
    if(num[x]>k)return ;
    st[++tot]=x,St[++tot1]=x;
    link(x){
	if(vis[j->t]||j->t==pre)continue;
	dis[j->t]=dis[x]+j->v;
	_dfs(j->t,x);
    }
}

void solve(int x){
    vis[x]=1;tot1=0;c1[1]=1;MAxx[1]=0;
    link(x){
	if(vis[j->t])continue;
	tot=0;num[x]=1;dis[j->t]=j->v;_dfs(j->t,x);
	inc(i,1,tot){
	    if(dis[st[i]]+MAxx[k+1-num[st[i]]]>ans1)ans1=dis[st[i]]+MAxx[k+1-num[st[i]]],ans2=c1[k+1-num[st[i]]];
	    else if(dis[st[i]]+MAxx[k+1-num[st[i]]]==ans1)ans2+=c1[k+1-num[st[i]]];
	}
	inc(i,1,tot){
	    if(MAxx[num[st[i]]]==dis[st[i]])c1[num[st[i]]]++;
	    else if(MAxx[num[st[i]]]<dis[st[i]])MAxx[num[st[i]]]=dis[st[i]],c1[num[st[i]]]=1;
	}
    }
    inc(i,1,tot1)MAxx[num[St[i]]]=-inf,c1[num[St[i]]]=0;
    c1[1]=0;MAxx[1]=-inf;
    link(x){
	if(vis[j->t])continue;
	base=sz[j->t];key=(1<<30);get_root(j->t,0);
	solve(rt);
    }
}

int main(){
    n=read();m=read();k=read();
    inc(i,0,n)MAxx[i]=-inf;
    int x,y,z;
    inc(i,1,m)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z),Edge[i]=(Node){x,y,z};
    dij(1);
    memset(h,0,sizeof(h));memset(e,0,sizeof(e));o=e;
    inc(i,1,n)vis[i]=dis[i]=0;
    inc(i,1,n)sort(vec[i].begin(),vec[i].end());
    dfs(1);
    inc(i,1,n)vis[i]=0;
    key=(1<<30);base=n;get_root(1,0);
    solve(rt);
    printf("%lld %lld\n",ans1,ans2);
    return 0;
}

题目描述

给一个包含$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$行，每行三个正整数$A_i,B_i,C_i(1<=A_i,B_i<=n,1<=C_i<=10000)$，表示$A_i$和$B_i$间有一条长度为$C_i$的边。数据保证输入的是连通的无向图。

Output

输出一行两个整数，以一个空格隔开，第一个整数表示包含$K$个点的路径最长为多长，第二个整数表示这样的不同的最长路径有多少条。