题目链接：https://www.luogu.com.cn/problem/P1073
题目大意：给定一张有向图 , 其中每个点有一个权值 (w), 求出 (1) 到 (n) 的所有路径中 (w_i - w_j) ( (i) , (j) 为同一条路径上的两个节点 , 且 (i) 比 (j) 后遍历到 ) 的最大值
solution
算法一:
设从 1 到 (i) 所有路径上节点权值的最大值为 (g_i) , (i) 到 (n) 所有路径上节点权值的最小值为 (f_i) , 可以用SPFA分别求出这两个值 , 再遍历每个节点 , 求得 (maxleft{g_i - f_i ight}(i leq n))即为答案
复杂度: (O(km)) ~ (O(nm))
code
#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &FF) {
int RR = 1; FF = 0; char CH = getchar();
for(; !isdigit(CH); CH = getchar()) if(CH == '-') RR = -RR;
for(; isdigit(CH); CH = getchar()) FF = FF * 10 + CH - 48;
FF *= RR;
}
inline void file(string str) {
freopen((str + ".in").c_str(), "r", stdin);
freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 1e6 + 10;
int n, m, now, fst[N], nxt[N], num[N], wi[N], ans;
int ni, ft[N], nt[N], nm[N];
void add(int u, int v, int k) {
nxt[++now] = fst[u], fst[u] = now, num[now] = v;
nt[++ni] = ft[v], ft[v] = ni, nm[ni] = u;
if(k) {
nxt[++now] = fst[v], fst[v] = now, num[now] = u;
nt[++ni] = ft[u], ft[u] = ni, nm[ni] = v;
}
}
int vis[N], ma[N], mi[N];
void Spfa_max() {
queue<int> qi;
qi.push(n); vis[n] = true; ma[n] = wi[n];
while(!qi.empty()) {
int pi = qi.front(); qi.pop(); vis[pi] = false;
for(int i = ft[pi]; i; i = nt[i])
if(max(ma[pi], wi[nm[i]]) > ma[nm[i]]) {
ma[nm[i]] = max(ma[pi], wi[nm[i]]);
if(!vis[nm[i]]) qi.push(nm[i]), vis[nm[i]] = true;
}
}
}
void Spfa_min() {
queue<int> qi;
memset(vis, 0, sizeof(vis));
memset(mi, 0x3f, sizeof(mi));
qi.push(1); vis[1] = true; mi[1] = wi[1];
while(!qi.empty()) {
int pi = qi.front(); qi.pop(); vis[pi] = false;
for(int i = fst[pi]; i; i = nxt[i])
if(min(mi[pi], wi[num[i]]) < mi[num[i]]) {
mi[num[i]] = min(mi[pi], wi[num[i]]);
if(!vis[num[i]]) qi.push(num[i]), vis[num[i]] = true;
}
}
}
int main() {
//file("");
int u, v, k;
read(n), read(m);
for(int i = 1; i <= n; i++) read(wi[i]);
for(int i = 1; i <= m; i++)
read(u), read(v), read(k), add(u, v, k - 1);
Spfa_max(), Spfa_min();
for(int i = 1; i <= n; i++)
ans = max(ans, ma[i] - mi[i]);
cout << ans << endl;
return 0;
}
算法二:
建三张一模一样的分层图 , 其中每个分层图内路径长度为 0 , 相邻两张分层图中从 (i) 到 (i) 连边 , 其中一号图与二号图间 (i) 号节点连边的长度设为 (-w_i) , 意为从 (i) 号节点买进 , 二号图与三号图间 (i) 号节点连边的长度设为 (w_i) 意为从 (i) 号节点卖出 , 这样从一号图中的 1号节点到三号图中 (n) 号节点的最长路即为答案 , 可用SPFA求出
复杂度: (O(km)) ~ (O(nm))
code
#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &FF) {
int RR = 1; FF = 0; char CH = getchar();
for(; !isdigit(CH); CH = getchar()) if(CH == '-') RR = -RR;
for(; isdigit(CH); CH = getchar()) FF = FF * 10 + CH - 48;
FF *= RR;
}
inline void file(string str) {
freopen((str + ".in").c_str(), "r", stdin);
freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 3e6 + 10;
int n, m, now, fst[N], nxt[N], num[N], wi[N], vi[N];
void add(int u, int v, int w) {
nxt[++now] = fst[u], fst[u] = now, num[now] = v, wi[now] = w;
}
void Add_edge(int u, int v, int k) {
add(u, v, 0), add(n + u, n + v, 0), add(n * 2 + u, n * 2 + v, 0);
if(k == 2) add(v, u, 0), add(n + v, n + u, 0), add(n * 2 + v, n * 2 + u, 0);
}
int vis[N], lt[N];
void Spfa() {
memset(lt, 0x80, sizeof(lt));
queue<int> qi; qi.push(1); vis[1] = true, lt[1] = 0;
while(!qi.empty()) {
int pi = qi.front(); qi.pop(); vis[pi] = false;
for(int i = fst[pi]; i; i = nxt[i])
if(lt[pi] + wi[i] > lt[num[i]]) {
lt[num[i]] = lt[pi] + wi[i];
if(!vis[num[i]]) qi.push(num[i]), vis[num[i]] = true;
}
}
}
int main() {
//file("");
int u, v, k;
read(n), read(m);
for(int i = 1; i <= n; i++) read(vi[i]);
for(int i = 1; i <= m; i++)
read(u), read(v), read(k), Add_edge(u, v, k);
for(int i = 1; i <= n; i++) add(i, i + n, -vi[i]), add(n + i, n * 2 + i, vi[i]);
n = n * 3; Spfa();
cout << max(lt[n], 0) << endl;
return 0;
}