描述

就是求兩對點之間 (s1,t1 和 s2,t2) 最短路的最長重合距離

分析

• 首先要有可以快速判斷一條邊是否在最短路上的方法, 可以用SPFA分別跑出以s1, t1, s2, t2四個點為起點的單源最短路, 判斷時例如如果 d_s1[u] + d_t1[e.to] + e.dist == d_s1[t1], 那么邊就在s1, t1的最短路上.
• 確定一些在最短路上的邊后就可以用拓?fù)渑判蚯蟪鲎铋L路. 注意把s2, t2反過來再做一次
• 拓?fù)渑判驎r注意判斷點有沒有在最短路上

代碼
#include #include #include #include #include using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 1500 + 10; int d_s1[maxn], d_t1[maxn], d_s2[maxn], d_t2[maxn]; struct Edge { int to, dist; }; struct SPFA { int n, m; bool inq[maxn]; vectoredges; vectorG[maxn]; void init(int n) { this->n = n; } void AddEdge(int from, int to, int dist) { edges.push_back((Edge){to, dist}); edges.push_back((Edge){from, dist}); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } void spfa(int *d, int s) { queueQ; memset(inq, 0, sizeof(inq)); for(int i = 1; i <= n; i++) d[i] = INF; Q.push(s); inq[s] = 1; d[s] = 0; while(!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = 0; for(int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if(d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; if(!inq[e.to]) Q.push(e.to), inq[e.to] = 1; } } } } }g1; struct TOPO { int n, m, d[maxn], d0[maxn]; vectoredges; vectorG[maxn]; void init(int n) { this->n = n; memset(d0, 0, sizeof(d0)); edges.clear(); for(int u = 1; u <= n; u++) G[u].clear(); } void AddEdge(int from, int to, int dist) { edges.push_back((Edge){to, dist}); m = edges.size(); G[from].push_back(m-1); d0[to]++; } int toposort() { queueQ; memset(d, 0, sizeof(d)); for(int u = 1; u <= n; u++) if(G[u].size() != 0 && !d0[u]) Q.push(u); int max_d = 0; while(!Q.empty()) { int u = Q.front(); Q.pop(); max_d = max(max_d, d[u]); for(int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; d[e.to] = max(d[e.to], d[u] + e.dist); if(--d0[e.to] == 0) Q.push(e.to); } } return max_d; } }g2; int main() { int n, m, s1, t1, s2, t2; scanf("%d %d %d %d %d %d", &n, &m, &s1, &t1, &s2, &t2); g1.init(n); for(int i = 0; i < m; i++) { int from, to, dist; scanf("%d %d %d", &from, &to, &dist); g1.AddEdge(from, to, dist); } g1.spfa(d_s1, s1); g1.spfa(d_t1, t1); g1.spfa(d_s2, s2); g1.spfa(d_t2, t2); int ans = 0; g2.init(n); for(int u = 1; u <= n; u++) for(int i = 0; i < g1.G[u].size(); i++) { Edge& e = g1.edges[g1.G[u][i]]; if(d_s1[u] + d_t1[e.to] + e.dist == d_s1[t1] && d_s2[u] + d_t2[e.to] + e.dist == d_s2[t2]) g2.AddEdge(u, e.to, e.dist); } ans = max(ans, g2.toposort()); g2.init(n); for(int u = 1; u <= n; u++) for(int i = 0; i < g1.G[u].size(); i++) { Edge& e = g1.edges[g1.G[u][i]]; if(d_s1[u] + d_t1[e.to] + e.dist == d_s1[t1] && d_s2[e.to] + d_t2[u] + e.dist == d_s2[t2]) g2.AddEdge(u, e.to, e.dist); } ans = max(ans, g2.toposort()); printf("%d\n", ans); return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ-1880-Elaxia的路线-SDOI2009-SPFA+拓扑排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。