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;
}