HYSBZ - 4016 最短路径树问题 点分治 + 最短路径最小字典序

题目传送门

题解：首先对于给定的图，需要找到那些从1好点出发然后到x号点的最短路， 如果有多条最短路就要找到字典序最小的路，这样扣完这些边之后就会有一棵树。然后再就是很普通的点分治了。

对于扣边这个问题， 我们先跑一遍最短路，这样就可以得到1号点到其他的点的距离。

然后在跑一遍dfs， 我们在跑dfs找路的时候， 可以通过 d[u] + ct[i] == d[v] 来判断是不是最短路是否可以走这条边， 然后我们再从所有可能边中的最小编号出发，这样我们就能保证字典序最小了。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define lch(x) tr[x].son[0]

 #define rch(x) tr[x].son[1]

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod =  (int)1e9+;

 const int N = 3e4 + ;

 vector<pll> vc[N];

 int d[N];

 void dij(){

     memset(d, inf, sizeof(d));

     priority_queue<pll, vector<pll>, greater<pll> > q;

     d[] = ;

     q.push(pll(,));

     int x, dd, v, ct;

     while(!q.empty()){

         x = q.top().se, dd = q.top().fi;

         q.pop();

         if(dd != d[x]) continue;

         for(int i = ; i < vc[x].size(); ++i){

             v = vc[x][i].fi , ct = vc[x][i].se;

             if(d[v] > d[x] + ct){

                 d[v] = d[x] + ct;

                 q.push(pll(d[v], v));

             }

         }

     }

     return;

 }

 int vis[N];

 int head[N], to[N<<], val[N<<], nt[N<<], tot = ;

 void add(int u, int v, int ct){

     to[tot] = v;

     val[tot] = ct;

     nt[tot] = head[u];

     head[u] = tot++;

     return ;

 }

 void dfs(int u){

     vis[u] = ;

     int v, dd;

     for(int i = ; i < vc[u].size(); i++){

         v = vc[u][i].fi, dd = vc[u][i].se;

         if(vis[v] || d[v] != d[u] + dd) continue;

         add(u, v, dd);

         add(v, u, dd);

         dfs(v);

     }

     return ;

 }

 int sz[N];

 int rt, minval;

 int n, m, k;

 void get_rt(int o, int u, int num){

     sz[u] = ;

     int v;

     int maxval = ;

     for(int i = head[u]; ~i; i = nt[i]){

         v = to[i];

         if(v == o || vis[v]) continue;

         get_rt(u, v, num);

         sz[u] += sz[v];

         maxval = max(maxval, sz[v]);

     }

     if(o) maxval = max(maxval, num - sz[u]);

     if(maxval < minval){

         minval = maxval;

         rt = u;

     }

 }

 int fans = , fcnt = ;

 int cnt[N], dis[N];

 void Update(int vval, int num){

     if(fans == vval) fcnt += num;

     else if(fans < vval) fans = vval, fcnt = num;

     return ;

 }

 void Dfs(int o, int u, int w, int num){

     sz[u] = ;

     if(num == k-)

         Update(w, );

     if(k >= num && dis[k-num]){

         Update(w+dis[k-num], cnt[k-num]);

     }

     for(int i = head[u]; ~i; i = nt[i]){

         int v = to[i];

         if(v == o || vis[v]) continue;

         Dfs(u, v,w+val[i], num+);

         sz[u] += sz[v];

     }

     return ;

 }

 void Change(int o, int u, int w, int num, int op){

     if(num >= k) return ;

     if(op == ) {

         if(dis[num+] < w) dis[num+] = w, cnt[num+] = ;

         else if(dis[num+] == w) cnt[num+]++;

     }

     else dis[num+] = cnt[num+] = ;

     for(int i = head[u]; ~i; i = nt[i]){

         int v = to[i];

         if(v == o || vis[v]) continue;

         Change(u, v, w+val[i], num+, op);

     }

     return ;

 }

 void solve(int x, int num){

     if(num <= ) return ;

     minval = inf;

     get_rt(, x, num);

     vis[rt] = ;

     int v;

     for(int i = head[rt]; ~i; i = nt[i]){

         v = to[i];

         if(vis[v]) continue;

         Dfs(, v, val[i], );

         Change(, v, val[i], , );

     }

     for(int i = head[rt]; ~i; i = nt[i]){

         v = to[i];

         if(vis[v]) continue;

         Change(, v, val[i], , );

     }

     for(int i = head[rt]; ~i; i = nt[i]){

         v = to[i];

         if(vis[v]) continue;

         solve(v, sz[v]);

     }

     return ;

 }

 int main(){

     int u, v, w;

     memset(head, -, sizeof(head));

     scanf("%d%d%d", &n, &m, &k);

     for(int i = ; i <= m; i++){

         scanf("%d%d%d", &u, &v, &w);

         vc[u].pb(pll(v,w));

         vc[v].pb(pll(u,w));

     }

     dij();

     dfs();

     memset(vis, , sizeof(vis));

     solve(, n);

     printf("%d %d", fans, fcnt);

     return ;

 }