tro str ins bsp pos head desc void size
给一个包含 n 个点,m 条边的无向连通图。从顶点 1 出发,往其余所有点分别走一次并返回。
往某一个点走时,选择总长度最短的路径走。若有多条长度最短的路径,则选择经过的顶点序列字典序最小的那条路径 (如路径 A 为 1,32,11,路径 B 为 1,3,2,11,路径 B 字典序较小。注意是序列的字典序的最小,而非路径中节点编号相连的字符串字典序最小)。到达该点后按原路返回,然后往其他点走,直到所有点都走过。
可以知道,经过的边会构成一棵最短路径树。请问,在这棵最短路径树上,最长的包含 K 个点的简单路径长度为多长?长度为该最长长度的不同路径有多少条?
这里的简单路径是指:对于一个点最多只经过一次的路径。不同路径是指路径两端端点至少有一个不同,点 A 到点 B 的路径和点 B 到点 A 视为同一条路径。
第一行输入三个正整数 n,m,K,表示有 n 个点 m 条边,要求的路径需要经过 K 个点。接下来输入 m 行,每行三个正整数 Ai,Bi,Ci(1<=Ai,Bi<=n,1<=Ci<=10000),表示 Ai 和 Bi 间有一条长度为 Ci 的边。数据保证输入的是连通的无向图。
输出一行两个整数,以一个空格隔开,第一个整数表示包含 K 个点的路径最长为多长,第二个整数表示这样的不同的最长路径有多少条。
6 6 4
1 2 1
2 3 1
3 4 1
2 5 1
3 6 1
5 6 1
3 4
对于所有数据 n<=30000,m<=60000,2<=K<=n。
数据保证最短路径树上至少存在一条长度为 K 的路径
2016.12.7 新加数据一组 by - wyx-150137
首先求字典序最小的最短路树,考虑将边拆成两条单向边,然后按终点从大到小排序,按序插入链式前向星中,保证找到的第一条最短路就是字典序最小的。点分就比较裸了,记深度为 $i$ 时最大的路径长度为 $sum_i$ ,长度为 $sum_i$ ,且深度为 $i$ 的路径数为 $cnt_i$ 直接转移就好了。[FJOI2014] 最短路径树问题
- #include < iostream > #include < cstdio > #include < cstring > #include < algorithm > #include < cmath > #include < queue > using namespace std;
- struct ZYYS {
- int u,
- v,
- d;
- }
- E[120001];
- struct Node {
- int next,
- to,
- d;
- }
- edge[200001];
- int num,
- head[30001],
- dist[30001],
- pre[30001],
- pred[30001];
- int size[30001],
- maxsize[30001],
- minsize,
- root,
- w[30001],
- k,
- ans,
- dep_max,
- n,
- m,
- cnt,
- c[300001];
- bool vis[30001];
- bool cmp(ZYYS a, ZYYS b) {
- if (a.u == b.u) return a.v > b.v;
- return a.u < b.u;
- }
- void add(int u, int v, int d) {
- num++;
- edge[num].next = head[u];
- head[u] = num;
- edge[num].to = v;
- edge[num].d = d;
- }
- void SPFA() {
- int i;
- queue < int > Q;
- memset(dist, 127 / 2, sizeof(dist));
- Q.push(1);
- dist[1] = 0;
- while (Q.empty() == 0) {
- int u = Q.front();
- Q.pop();
- vis[u] = 0;
- for (i = head[u]; i; i = edge[i].next) {
- int v = edge[i].to;
- if (dist[v] > dist[u] + edge[i].d) {
- pre[v] = u;
- pred[v] = edge[i].d;
- dist[v] = dist[u] + edge[i].d;
- if (vis[v] == 0) {
- vis[v] = 1;
- Q.push(v);
- }
- }
- }
- }
- }
- void get_size(int x, int pa) {
- int i;
- size[x] = 1;
- maxsize[x] = 0;
- for (i = head[x]; i; i = edge[i].next) {
- int v = edge[i].to;
- if (v == pa || vis[v]) continue;
- get_size(v, x);
- size[x] += size[v];
- maxsize[x] = max(maxsize[x], size[v]);
- }
- }
- void get_root(int x, int pa, int r) {
- int i;
- maxsize[x] = max(size[r] - size[x], maxsize[x]);
- if (maxsize[x] < minsize) {
- minsize = maxsize[x];
- root = x;
- }
- for (i = head[x]; i; i = edge[i].next) {
- int v = edge[i].to;
- if (v == pa || vis[v]) continue;
- get_root(v, x, r);
- }
- }
- void get_ans(int x, int pa, int dis, int dep) {
- int i;
- if (c[k - 1 - dep] && w[k - 1 - dep] + dis == ans) cnt += c[k - 1 - dep];
- else if (c[k - 1 - dep] && ans < w[k - 1 - dep] + dis) ans = w[k - 1 - dep] + dis,
- cnt = c[k - 1 - dep];
- dep_max = max(dep_max, dep);
- for (i = head[x]; i; i = edge[i].next) {
- int v = edge[i].to;
- if (v == pa || vis[v] || dep == k - 1) continue;
- get_ans(v, x, dis + edge[i].d, dep + 1);
- }
- }
- void get_update(int x, int pa, int dis, int dep) {
- int i;
- if (dis > w[dep]) w[dep] = dis,
- c[dep] = 1;
- else if (dis == w[dep]) c[dep]++;
- dep_max = max(dep_max, dep);
- for (i = head[x]; i; i = edge[i].next) {
- int v = edge[i].to;
- if (v == pa || vis[v] || dep == k - 1) continue;
- get_update(v, x, dis + edge[i].d, dep + 1);
- }
- }
- void slove(int x) {
- int i;
- minsize = 2e9;
- get_size(x, 0);
- get_root(x, 0, x);
- vis[root] = 1;
- dep_max = 0;
- c[0] = 1;
- for (i = head[root]; i; i = edge[i].next) {
- int v = edge[i].to;
- if (vis[v]) continue;
- get_ans(v, root, edge[i].d, 1);
- get_update(v, root, edge[i].d, 1);
- }
- for (i = 0; i <= dep_max; i++) w[i] = 0,
- c[i];
- for (i = head[root]; i; i = edge[i].next) {
- int v = edge[i].to;
- if (vis[v] == 0) slove(v);
- }
- }
- int main() {
- int i,
- u,
- v,
- d;
- cin >> n >> m >> k;
- for (i = 1; i <= m; i++) {
- scanf("%d%d%d", &u, &v, &d);
- E[2 * i - 1].u = u,
- E[2 * i - 1].v = v,
- E[2 * i - 1].d = d;
- E[2 * i].u = v;
- E[2 * i].v = u,
- E[2 * i].d = d;
- }
- sort(E + 1, E + 2 * m + 1, cmp);
- for (i = 1; i <= 2 * m; i++) {
- add(E[i].u, E[i].v, E[i].d);
- }
- SPFA();
- memset(head, 0, sizeof(head));
- num = 0;
- for (i = 2; i <= n; i++) add(i, pre[i], pred[i]),
- add(pre[i], i, pred[i]);
- slove(1);
- cout << ans << '' << cnt << endl;
- }
来源: http://www.bubuko.com/infodetail-2450717.html