HYSBZ 4016 最短路径树问题

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

Sample Output

3 4

Hint

对于所有数据n<=30000,m<=60000，2<=K<=n。数据保证最短路径树上至少存在一条长度为K的路径。

先用dijkstra加堆优化把图转化为树，然后就是树分治了。

#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF = 0x7FFFFFFF;
const int maxn = 2e5 + 10;
int n, m, x, y, z, K;
char ch;

struct Tree
{
  int ft[maxn], nt[maxn], u[maxn], v[maxn], sz, n;
  int vis[maxn], cnt[maxn], mx[maxn], a, b;
  void clear(int n)
  {
    this->n = n;
    a = b = sz = 0;
    for (int i = 1; i <= n; i++)
    {
      ft[i] = -1;
      vis[i] = 0;
    }
  }
  void AddEdge(int x, int y, int z)
  {
    u[sz] = y;  v[sz] = z;
    nt[sz] = ft[x]; ft[x] = sz++;
  }
  int dfs(int x, int fa, int sum)
  {
    int ans = mx[x] = 0;
    cnt[x] = 1;
    for (int i = ft[x]; i != -1; i = nt[i])
    {
      if (vis[u[i]] || u[i] == fa) continue;
      int y = dfs(u[i], x, sum);
      if (mx[y]<mx[ans]) ans = y;
      cnt[x] += cnt[u[i]];
      mx[x] = max(mx[x], cnt[u[i]]);
    }
    mx[x] = max(mx[x], sum - cnt[x]);
    return mx[x] < mx[ans] ? x : ans;
  }
  int deep(int x, int fa, int dep)
  {
    if (dep == K) return K - 1;
    int ans = dep;
    mx[dep] = cnt[dep] = 0;
    for (int i = ft[x]; i != -1; i = nt[i])
    {
      if (vis[u[i]] || u[i] == fa) continue;
      ans = max(ans, deep(u[i], x, dep + 1));
    }
    return ans;
  }
  void get(int x, int fa, int dep, int len, int kind, int lit)
  {
    if (dep == K) return;
    if (!kind)
    {
      if (K - 1 - dep <= lit && cnt[K - 1 - dep])
      {
        if (a<len + mx[K - 1 - dep])
        {
          a = len + mx[K - 1 - dep];
          b = cnt[K - 1 - dep];
        }
        else if (a == len + mx[K - 1 - dep]) b += cnt[K - 1 - dep];
      }
    }
    else
    {
      if (mx[dep]<len) mx[dep] = len, cnt[dep] = 1;
      else if (mx[dep] == len) cnt[dep]++;
    }
    for (int i = ft[x]; i != -1; i = nt[i])
    {
      if (vis[u[i]] || u[i] == fa) continue;
      get(u[i], x, dep + 1, len + v[i], kind, lit);
    }
  }
  void find(int x)
  {
    int len = deep(x, -1, 0);
    if (len + len + 1 < K) return;
    cnt[0] = 1;
    for (int i = ft[x]; i != -1; i = nt[i])
    {
      if (vis[u[i]]) continue;
      get(u[i], x, 1, v[i], 0, len);
      get(u[i], x, 1, v[i], 1, len);
    }
  }
  void work(int x, int sum)
  {
    mx[0] = INF;
    int y = dfs(x, -1, sum);
    vis[y] = 1; find(y);
    for (int i = ft[y]; i != -1; i = nt[i])
    {
      if (vis[u[i]]) continue;
      if (cnt[u[i]]<cnt[y]) work(u[i], cnt[u[i]]);
      else work(u[i], sum - cnt[y]);
    }
  }
}solve;

struct DAG
{
  int ft[maxn], nt[maxn], u[maxn], v[maxn], sz, n;
  int dis[maxn], vis[maxn];
  struct point
  {
    int x, y;
    point(int x = 0, int y = 0) :x(x), y(y) {}
    bool operator<(const point& a)const
    {
      return y == a.y ? x > a.x : y >a.y;
    }
  };
  void clear(int n)
  {
    this->n = n; sz = 0;
    for (int i = 1; i <= n; i++)
    {
      ft[i] = dis[i] = -1;
      vis[i] = 0;
    }
  }
  void AddEdge(int x, int y, int z)
  {
    u[sz] = y;  v[sz] = z;
    nt[sz] = ft[x]; ft[x] = sz++;
  }
  void dfs(int x)
  {
    vis[x] = 0;
    for (int i = ft[x]; i != -1; i = nt[i])
    {
      if (dis[u[i]] == dis[x] + v[i])
      {
        if (!vis[u[i]]) continue;
        solve.AddEdge(x, u[i], v[i]);
        solve.AddEdge(u[i], x, v[i]);
        dfs(u[i]);
      }
    }
  }
  void dijkstra()
  {
    priority_queue<point> p;
    p.push(point(1, dis[1] = 0));
    while (!p.empty())
    {
      point q = p.top();  p.pop();
      if (vis[q.x]) continue; else vis[q.x] = 1;
      for (int i = ft[q.x]; i != -1; i = nt[i])
      {
        if (dis[u[i]] == -1 || dis[u[i]] > q.y + v[i])
        {
          p.push(point(u[i], dis[u[i]] = q.y + v[i]));
        }
      }
    }
    solve.clear(n);
    dfs(1);
    solve.work(1, n);
    printf("%d %d\n", solve.a, solve.b);
  }
}dag;

void read(int &x)
{
  while ((ch = getchar()) < '0' || ch > '9');
  x = ch - '0'; 
  while ((ch = getchar()) >= '0' && ch <= '9') x = x * 10 + ch - '0';
}

struct point
{
  int x, y, z;
  void scan() { read(x); read(y); read(z); }
  bool operator<(const point &a)const
  {
    return x == a.x ? y > a.y:x < a.x;
  }
}p[maxn];

int main()
{
  while (~scanf("%d%d%d", &n, &m, &K))
  {
    dag.clear(n);
    for (int i = 0; i < m + m; i += 2)
    {
      p[i].scan();
      p[i ^ 1] = p[i];
      swap(p[i ^ 1].x, p[i ^ 1].y);
    }
    sort(p, p + m + m);
    for (int i = 0; i < m + m; i++)
    {
      dag.AddEdge(p[i].x, p[i].y, p[i].z);
    }
    dag.dijkstra();
  }
  return 0;
}