首页 > 代码库 > bzoj1880: [Sdoi2009]Elaxia的路线
bzoj1880: [Sdoi2009]Elaxia的路线
1880: [Sdoi2009]Elaxia的路线
Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 1035 Solved: 412
[Submit][Status][Discuss]
Description
最近，Elaxia和w**的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们 必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和实验室之间，他们 希望在节约时间的前提下，一起走的时间尽可能的长。 现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图：地图上有N个路 口，M条路，经过每条路都需要一定的时间。 具体地说，就是要求无向图中，两对点间最短路的最长公共路径。
Input
第一行：两个整数N和M（含义如题目描述）。 第二行：四个整数x1、y1、x2、y2（1 ≤ x1 ≤ N，1 ≤ y1 ≤ N，1 ≤ x2 ≤ N，1 ≤ ≤ N），分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号（两对点分别 x1,y1和x2,y2）。 接下来M行：每行三个整数，u、v、l（1 ≤ u ≤ N，1 ≤ v ≤ N，1 ≤ l ≤ 10000），表 u和v之间有一条路，经过这条路所需要的时间为l。 出出出格格格式式式：：： 一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）。
Output
一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）
Sample Input
9 10
1 6 7 8
1 2 1
2 5 2
2 3 3
3 4 2
3 9 5
4 5 3
4 6 4
4 7 2
5 8 1
7 9 1
1 6 7 8
1 2 1
2 5 2
2 3 3
3 4 2
3 9 5
4 5 3
4 6 4
4 7 2
5 8 1
7 9 1
Sample Output
3
HINT
对于30%的数据，N ≤ 100；
对于60%的数据，N ≤ 1000；
对于100%的数据，N ≤ 1500，输入数据保证没有重边和自环。
Source
Day2
分析：既然要求最长公共路径，那么就要求出在公共路径上的点，先用四次spfa把各个点的最短路算出来，然后联想到树网的核，可以知道如何判断点i是否在x,y上，如果d[xi] + d[iy] = d[xy],那么i就在x,y上，但是如果算出来的点在公共边上，可是连起来的边可能不在公共边上，怎么办呢？那么就把点改成边即可,设这个边的左端点为i,端点为j,如果d[xi] + d[ij] + d[jy] = d[xy],那么就在xy上，这样我们可以把这些边提出来，发现是一条条的链，然后就是求最长链，怎么求呢？可以用dp或者拓扑排序，对于这道题用拓扑排序，从小到大连边后，不断删除入度为0的点和其连接的边，同时更新答案即可.
代码参考了hahalidaxin神犇的（其实几乎一样啦）
#include <cstdio>#include <vector>#include <cstring>#include <iostream>#include <algorithm>#include <queue>using namespace std;const int maxn = 1510,inf = 1e9;struct node{ int u, v, w;};int n, m, x1, y1, x2, y2,ans,rudu[maxn],d[maxn],dx1[maxn],dx2[maxn],dy1[maxn],dy2[maxn],vis[maxn];vector <int> g1[maxn];vector <node> e, g2[maxn];void add1(int u, int v, int w){ node temp; temp.u = u; temp.v = v; temp.w = w; e.push_back(temp); g1[u].push_back((int)e.size() - 1);}void add2(int u, int v, int w){ node temp; temp.u = u; temp.v = v; temp.w = w; g2[u].push_back(temp); rudu[v]++;}void spfa(int s, int *d){ memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; i++) d[i] = inf; queue <int> q; d[s] = 0; vis[s] = 1; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = 0; i < g1[u].size(); i++) { node temp = e[g1[u][i]]; int v = temp.v; if (d[v] > d[u] + temp.w) { d[v] = d[u] + temp.w; if (!vis[v]) { vis[v] = 1; q.push(v); } } } }}void topo(){ queue <int> q; for (int i = 1; i <= n; i++) if (!rudu[i]) q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < g2[u].size(); i++) { int v = g2[u][i].v; if (d[v] < d[u] + g2[u][i].w) { d[v] = d[u] + g2[u][i].w; ans = max(ans, d[v]); } if (!(--rudu[v])) q.push(v); } }}int main(){ scanf("%d%d%d%d%d%d", &n, &m, &x1, &y1, &x2, &y2); for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add1(u, v, w); add1(v, u, w); } spfa(x1, dx1); spfa(x2, dx2); spfa(y1, dy1); spfa(y2, dy2); for (int i = 0; i < e.size(); i++) { int u = e[i].u, v = e[i].v, w = e[i].w; int len1 = min(dx1[u], dx1[v]) + min(dy1[u], dy1[v]) + w; int len2 = min(dx2[u], dx2[v]) + min(dy2[u], dy2[v]) + w; if (len1 == dx1[y1] && len2 == dx2[y2]) { if (dx1[u] < dx1[v]) add2(u, v, w); else add2(v, u, w); } } topo(); printf("%d", ans); return 0;}
bzoj1880: [Sdoi2009]Elaxia的路线
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。