做乘法的最短路時，若權(quán)值>=0，只能用spfa來做，相等于加法中的負權(quán)邊
1129. 熱浪
1129. 熱浪 - AcWing題庫
單源最短路，稀疏圖，用堆優(yōu)化Dijkstra即可，就是板子套了個背景
// 稀疏圖，用堆優(yōu)化Dijkstra存儲
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 2510, M = 2 * 6210;
typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII>> q;
int h[N], e[M], ne[M], w[M], idx = 1;
int n, m, start, ed;
int dis[N];
bool st[N];
void add(int x, int y, int d)
{
e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}
void dijkstra()
{
memset(dis, 0x3f, sizeof(dis));
dis[start] = 0;
q.push({0, start});
while (q.size())
{
auto t = q.top(); q.pop();
int x = t.second, d = t.first;
if (st[x]) continue;
st[x] = true;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (dis[y] > d + w[i])
{
dis[y] = d + w[i];
q.push({dis[y], y});
}
}
}
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d%d%d", &n, &m, &start, &ed);
int x, y, d;
for (int i = 1; i <= m; ++ i )
{
scanf("%d%d%d", &x, &y, &d);
add(x, y, d), add(y, x, d);
}
dijkstra();
printf("%d\n", dis[ed]);
return 0;
}
debug：由于是無向圖，邊的數(shù)量要開兩倍。但是w[N]沒改，debug了很久
所以e[M], ne[M], w[M]，只有h[N]，其他的數(shù)組存儲的都是邊
1128. 信使
1128. 信使 - AcWing題庫
單源最短路，稀疏圖，用堆優(yōu)化Dijkstra即可，最后統(tǒng)計所有dis的最大值并返回即可
// 單源最短路，最后將第1個點到其他點的距離累加即可
// 稀疏圖，依然是堆優(yōu)化的dijkstra
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110, M = 410;
int h[N], e[M], ne[M], w[M], idx = 1;
priority_queue<PII, vector<PII>, greater<PII>> q;
int n, m;
bool st[N]; int dis[N];
void add(int x, int y, int d)
{
e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}
void dijkstra()
{
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
q.push({0, 1});
while (q.size())
{
auto t = q.top(); q.pop();
int x = t.second, d = t.first;
if (st[x]) continue;
st[x] = true;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (dis[y] > d + w[i])
{
dis[y] = d + w[i];
q.push({dis[y], y});
}
}
}
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
int x, y, d;
for (int i = 1; i <= m; ++ i )
{
scanf("%d%d%d", &x, &y, &d);
add(x, y, d), add(y, x, d);
}
dijkstra();
int res = 0;
bool flag = true;
for (int i = 2; i <= n; ++ i )
{
if (dis[i] == 0x3f3f3f3f)
{
flag = false;
break;
}
res = max(res, dis[i]);
}
if (flag) printf("%d\n", res);
else puts("-1");
return 0;
}
debug：%d打成了5d，樂，竟然能編譯通過
判斷某個點的最短距離是否已經(jīng)確定，打成了if(dis[x]); dis[x] = true，這也debug了半天
1127. 香甜的黃油
1127. 香甜的黃油 - AcWing題庫
// 多源匯最短路，由于flody可能超時，所以用單源最短路求解
// 這里用spfa
#include <iostream>
#include <cstring>
using namespace std;
const int N = 810, M = 3000;
int h[N], e[M], ne[M], w[M], idx = 1;
int dis[N]; bool st[N];
int s, n, m;
int q[N];
int id[N];
void add(int x, int y, int d)
{
e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}
void spfa(int k)
{
memset(dis, 0x3f, sizeof(dis));
int hh = 0, tt = 1;
dis[k] = 0;
q[tt ++ ] = k, st[k] = true;
while (tt != hh)
{
int x = q[hh ++ ];
if (hh == N) hh = 0;
st[x] = false;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (dis[y] > dis[x] + w[i])
{
dis[y] = dis[x] + w[i];
if (!st[y])
{
q[tt ++ ] = y, st[y] = true;
if (tt == N) tt = 0;
}
}
}
}
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d%d", &s, &n, &m);
for (int i = 1; i <= s; ++ i ) scanf("%d", &id[i]);
int x, y, d;
for (int i = 1; i <= m; ++ i )
{
scanf("%d%d%d", &x, &y, &d);
add(x, y, d), add(y, x, d);
}
int res = 0x3f3f3f3f;
for (int i = 1; i <= n; ++ i )
{
spfa(i);
int sum = 0; bool flag = true;
for (int j = 1; j <= s; ++ j )
{
if (dis[id[j]] == 0x3f3f3f3f)
{
flag = false;
break;
}
sum += dis[id[j]];
}
if (flag) res = min(res, sum);
}
printf("%d\n", res);
return 0;
}
用自己寫的循環(huán)隊列代替queue，時間大概快了一倍
需要注意的是，循環(huán)隊列的hh和tt從0開始使用，并且都是后置++，++后還要維護循環(huán)性質(zhì)
以下是用queue實現(xiàn)的版本
// 多源匯最短路，由于flody可能超時，所以用單源最短路求解
// 這里用spfa
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 810, M = 1500 * 2;
int h[N], e[M], ne[M], w[M], idx = 1;
int dis[N]; bool st[N];
int s, n, m;
queue<int> q;
int id[N];
void add(int x, int y, int d)
{
e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}
void spfa(int k)
{
memset(dis, 0x3f, sizeof(dis));
dis[k] = 0;
q.push(k), st[k] = true;
while (q.size())
{
int x = q.front(); q.pop();
st[x] = false;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (dis[y] > dis[x] + w[i])
{
dis[y] = dis[x] + w[i];
if (!st[y]) q.push(y), st[y] = true;
}
}
}
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d%d", &s, &n, &m);
int t;
for (int i = 1; i <= s; ++ i ) scanf("%d", &id[i]);
int x, y, d;
for (int i = 1; i <= m; ++ i )
{
scanf("%d%d%d", &x, &y, &d);
add(x, y, d), add(y, x, d);
}
LL res = 1e18;
for (int i = 1; i <= n; ++ i )
{
spfa(i);
LL sum = 0; bool flag = true;
for (int i = 1; i <= s; ++ i )
{
if (dis[id[i]] == 0x3f3f3f3f)
{
flag = false;
break;
}
sum += dis[id[i]];
}
if (flag) res = min(res, sum);
}
printf("%lld\n", res);
return 0;
}
1126. 最小花費
1126. 最小花費 - AcWing題庫
轉(zhuǎn)賬金額A，當手續(xù)費的比例為z時，只能轉(zhuǎn)賬A(1 - z)
若每條邊的權(quán)值為實際轉(zhuǎn)賬的金額比例，那么從起點到終點，這個比例越大，花費的初始金額就越少，所以這題需要找一條從起點到終點比例最大的路徑
即從起點到終點經(jīng)過的所有邊的比例相乘最大，由于比例的大小為
0
<
z
<
=
1
0 < z <= 1
0<z<=1，所以這里初始化dis數(shù)組以及鄰接矩陣為全0
接著用spfa或者dijkstra求“最短路”即可
// 同樣的單源最短路，spfa解決
#include <iostream>
using namespace std;
const int N = 2010;
double g[N][N];
int n, m, start, ed;
double dis[N]; bool st[N];
int q[N], tt, hh;
void spfa()
{
dis[start] = 1.0;
q[tt ++ ] = start, st[start] = true;
while (tt != hh)
{
int x = q[hh ++ ];
if (hh == N) hh = 0;
st[x] = false;
for (int j = 1; j <= n; ++ j )
{
if (dis[j] < dis[x] * g[x][j])
{
dis[j] = dis[x] * g[x][j];
if (!st[j])
{
q[tt ++ ] = j, st[j] = true;
if (tt == N) tt = 0;
}
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
int x, y, z;
for (int i = 1; i <= m; ++ i )
{
scanf("%d%d%d", &x, &y, &z);
g[x][y] = g[y][x] = 1 - (z / 100.0);
}
scanf("%d%d", &start, &ed);
spfa();
printf("%.8lf\n", 100 / dis[ed]);
return 0;
}
920. 最優(yōu)乘車
920. 最優(yōu)乘車 - AcWing題庫
沒之前的題目裸，需要一些思考
雖然題目沒有給定邊的權(quán)重，但是給定了公交路線，可知公交路線
a
a
a中，
a
i
a_i
ai?到
a
j
a_j
aj?的權(quán)重為1，表示從i地到j地需要的乘車次數(shù)，當如
a
i
a_i
ai?在
a
a
a中的下標要出現(xiàn)在
a
j
a_j
aj?之前，這是一張有向圖
所以，根據(jù)題目給定的公交路線，找出圖中所有的有向邊，最后用單源最短路就行了
由于邊的權(quán)值為1，甚至用bfs也行
// 一條路線之間的點可達，存在有向邊，線路中有n個點，存在Cn2條邊
// 邊的權(quán)值為1，表示需要乘車的次數(shù)，由于權(quán)值為1，所以可以用bfs
#include <iostream>
#include <sstream>
#include <string>
#include <cstring>
using namespace std;
const int N = 510, M = 11;;
int a[N], g[N][N], q[N];
int dis[N];
int n, m, tt, hh;
int bfs()
{
dis[1] = 0;
q[tt ++ ] = 1;
while (tt != hh)
{
int x = q[hh ++ ];
if (hh == N) hh = 0;
for (int y = 1; y <= n; ++ y )
{
if (y != x && !dis[y] && g[x][y])
{
dis[y] = dis[x] + 1;
if (y == n) return dis[y];
q[tt ++ ] = y;
}
}
}
return 0;
}
int main()
{
scanf("%d%d", &m, &n);
string line;
getline(cin, line);
for (int i = 0; i < m; ++ i )
{
getline(cin, line);
stringstream s(line);
int idx = 0, p;
while (s >> p) a[idx ++ ] = p;
for (int j = 0; j < idx; ++ j )
for (int k = j + 1; k < idx; ++ k )
g[a[j]][a[k]] = 1;
}
int t = bfs();
if (t == 0) puts("NO");
else printf("%d\n", t - 1);
return 0;
}
903. 昂貴的聘禮
903. 昂貴的聘禮 - AcWing題庫
以下是我的思路，我只是記錄一下不建議看
要獲得某個物品，有兩種方式：1. 直接購買 2. 在擁有替代品的前提下，以優(yōu)惠價格購買
此外無法找出其他方法，需要考慮的是：以優(yōu)惠價格購買時，擁有替代品的代價是什么？
若從正面考慮，假設酋長的10000金幣是一個物品，現(xiàn)可以直接購買或者使用替代品。若使用替代品以更低的價格購買，那么購買替代品的價格是多少？同樣，購買替代品也有兩種方式，是直接購買省錢還是用替代品的替代品購買省錢。這是一個無止盡的過程，什么時候會停止？物品沒有替代品時停止，這就意味著我們要遞歸到最底部后，在向上回溯的過程中，才能計算兩種方式中哪種最省錢
這是直接的思路，可能能做出來吧，沒試過
正解：
將酋長的10000金幣看成物品，并且是有向圖的終點。物品之間有什么關(guān)系？從一個點走到另一個點，前提是當前點是下一點的替代品，那么從當前點到下一點的代價就是用當前物品購買下一物品的優(yōu)惠價格
所以邊的權(quán)重為優(yōu)惠價格，當前除了以優(yōu)惠價格購買，還能直接購買。直接購買時，當前點的含義不再是一個物品，所以這里的點是一個虛擬點，到其他點的權(quán)重為直接購買的價格
若當前已經(jīng)購買了物品，走向下一物品時，直接購買的價格肯定比使用替代品高，所以不用設置已經(jīng)購買物品時，再直接購買其他物品的邊。這樣的邊沒有意義
由于存在一些物品無法使用替代品購買，所以只要設置手上沒有物品時，直接購買物品的邊
虛擬點為上圖的s
起點為s，終點為1號物品（酋長的10000金幣），跑一個最短路即可
為什么起點是s？存在一些只能直接購買的物品
最后考慮等級限制，等級差距不超過m的人可以交換物品，由于題目數(shù)據(jù)量小，可以直接暴力枚舉。假設酋長的等級為a，那么需要枚舉的區(qū)間為 [ a ? m , a + m ] [a-m, a+m] [a?m,a+m]，枚舉這個區(qū)間中長度為m的區(qū)間，每次枚舉跑一次最短路即可
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int dis[N], g[N][N];
int level[N];
bool st[N];
int n, m;
int dijkstra(int l, int r)
{
memset(dis, 0x3f, sizeof(dis));
memset(st, false, sizeof(st));
dis[0] = 0;
for (int i = 0; i <= n; ++ i )
{
int t = -1;
for (int j = 0; j <= n; ++ j)
if (!st[j] && (t == -1 || dis[j] < dis[t])) t = j;
st[t] = true;
for (int j = 1; j <= n; ++ j )
if (l <= level[j] && level[j] <= r)
dis[j] = min(dis[j], dis[t] + g[t][j]);
}
return dis[1];
}
int main()
{
memset(g, 0x3f, sizeof(g));
scanf("%d%d", &m, &n);
int p, x, t, v;
for (int i = 1; i <= n; ++ i ) g[i][i] = 0;
for (int i = 1; i <= n; ++ i )
{
scanf("%d%d%d", &p, &level[i] , &x);
g[0][i] = min(g[0][i], p);
while ( x -- )
{
scanf("%d%d", &t, &v);
g[t][i] = min(g[t][i], v);
}
}
int res = 0x3f3f3f3f;
for (int i = level[1] - m; i <= level[1]; ++ i )
{
int t = dijkstra(i, i + m);
res = min(t, res);
}
printf("%d\n", res);
return 0;
}
1135. 新年好
1135. 新年好 - AcWing題庫
先用堆優(yōu)dijkstra跑單源最短路，一共是6個源點，分別是家所在的點以及親戚所在的點，保存最短距離
然后dfs爆搜，以1號點為起點，剩下五個點的全排列為搜索順序，記錄全排列中路徑的最短距離
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 5e5 + 10, M = 2e5 + 10;
const int INF = 1e9;
int h[N], e[M], ne[M], w[M], idx = 1;
int dis[6][N]; bool st[N];
int tar[10];
int n, m;
typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII>> q;
void add(int x, int y, int d)
{
e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}
void dijkstra(int start, int si) // si為start在dis數(shù)組中的一維下標
{
memset(st, false, sizeof(st));
dis[si][start] = 0;
q.push({ 0, start });
while (q.size())
{
auto t = q.top(); q.pop();
int x = t.second, d = t.first;
if (st[x]) continue;
st[x] = true;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (dis[si][y] > d + w[i])
{
dis[si][y] = d + w[i];
q.push({ dis[si][y], y});
}
}
}
}
int dfs(int cnt, int si, int d) // cnt為已經(jīng)拜訪的親戚數(shù)量，si為當前所在點在dis數(shù)組中的一維下標，d為遞達當前點的“距離”
{
if (cnt == 5) return d;
int res = INF;
for (int i = 1; i <= 5; ++ i )
{
if (!st[i])
{
int y = tar[i]; // 要訪問的下一個點在圖中的編號
st[i] = true;
res = min(res, dfs(cnt + 1, i, d + dis[si][y]));
st[i] = false;
}
}
return res;
}
int main()
{
memset(h, -1, sizeof(h));
memset(dis, 0x3f, sizeof(dis));
scanf("%d%d", &n, &m);
for ( int i = 1; i <= 5; ++ i ) scanf("%d", &tar[i]);
int x, y, t;
while ( m -- )
{
scanf("%d%d%d", &x, &y, &t);
add(x, y, t), add(y, x, t);
}
dijkstra(1, 0);
for (int i = 1; i <= 5; ++ i ) dijkstra(tar[i], i);
memset(st, false, sizeof(st));
printf("%d\n", dfs(0, 0, 0));
return 0;
}
debug：雙向邊，M又少開一倍，但是TLE，以后M都開兩倍吧，這太難調(diào)試了
dfs最后要返回res，因為min要使用dfs的返回值
340. 通信線路
340. 通信線路 - AcWing題庫
分析題意：對于每條1~n的路徑，我們只要支付第k+1大的邊的金額即可。若邊的數(shù)量少于k+1，那么支付金額為0
所以本題的最短路，短在第k+1大的邊權(quán)中，最小的那個。所有最大中找最小，自然地想到二分。二分邊權(quán)，得到ans，使得ans是所有1~n路徑中，第k+1大的權(quán)值中最小的那個
二分的范圍：
[
0
,
1
e
6
+
1
]
[0, 1e6+1]
[0,1e6+1]，權(quán)值最小值-1~權(quán)值最大值+1
check：分析ans的性質(zhì)，所有1~n的路徑中，第k+1大的邊權(quán)中最小值為ans
說明至少存在一條路徑，經(jīng)過了k條邊權(quán)大于ans的邊，即and是這條路徑中第k+1大的邊
那么其他路徑就一定經(jīng)過了多于k條權(quán)值大于ans的邊
由此得到check的檢查邏輯：根據(jù)參數(shù)x，判斷1~n的所有路徑中，是否存在一條路徑，經(jīng)過了小于等于k條的權(quán)值大于x的邊。若存在返回true，否則返回false
試想一下，x越大，check的性質(zhì)越容易滿足，x越小，性質(zhì)越難滿足
兩種特殊情況：ans為0，說明1~n的所有路徑中，至少存在一條路徑，經(jīng)過了k條權(quán)值大于0的邊，那么第k+1條邊的權(quán)值為0，需要支付金額為0
ans為
1
e
6
+
1
1e6+1
1e6+1，說明1n的所有路徑中，至少存在一條路徑，經(jīng)過了k條權(quán)值大于$1e6+1$的邊，由于邊權(quán)最大為$1e6$，所以這樣的路徑是不存在的，即1n之間不連通
如何得知1~n的所有路徑中，經(jīng)過了幾條權(quán)值大于x的邊？
對于權(quán)值大于x的邊，將其權(quán)值設置為1，否則設置為0，跑一遍最短路，就能知道1~n的最短路徑經(jīng)過了幾條權(quán)值大于x的邊
對于權(quán)值只有0和1的最短路問題，可以用雙端隊列bfs
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
const int N = 1010, M = 20010;
int n, p, k;
int h[N], e[M], ne[M], w[M], idx = 1;
int dis[N]; bool st[N];
deque<int> q;
void add(int x, int y, int d)
{
e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}
bool check(int bound)
{
memset(dis, 0x3f, sizeof(dis));
memset(st, false, sizeof(st));
dis[1] = 0;
q.push_back(1);
while (q.size())
{
int x = q.front(); q.pop_front();
if (st[x]) continue;
st[x] = true;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i], d = w[i] > bound;
if (dis[y] > dis[x] + d)
{
dis[y] = dis[x] + d;
if (d) q.push_back(y);
else q.push_front(y);
}
}
}
return dis[n] <= k;
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d%d", &n, &p, &k);
int x, y, d;
while ( p -- )
{
scanf("%d%d%d", &x, &y, &d);
add(x, y, d), add(y, x, d);
}
int l = 0, r = 1e6 + 1;
while ( l < r )
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (l == 1e6 + 1) puts("-1");
else printf("%d\n", l);
return 0;
}
342. 道路與航線
342. 道路與航線 - AcWing題庫
直接用spfa會被卡兩個數(shù)據(jù)
根據(jù)題意：道路，雙向邊，存在環(huán)，正權(quán)；航線：單向邊，無環(huán)，負權(quán)
其中關(guān)于是否有環(huán)以及權(quán)值的正負是選擇算法的關(guān)鍵
若圖中沒有負權(quán)邊，直接用堆d
若圖中無環(huán)，直接按照拓撲序遍歷所有點就能確定最短路
結(jié)合以上兩者，可以得到以下算法：
將所有點根據(jù)道路的連通性分成多個連通塊，每個連通塊之間不連通
連通每個連通塊的是航線，單向邊。讀取所有的航線后，按照拓撲序遍歷每個連通塊，對于每個連通塊，跑堆d求最短路
用id數(shù)組表示每個點所屬的連通塊編號，用二維數(shù)組blocks存儲每個連通塊中點的編號
讀入所有道路后，dfs可以遍歷連通塊中的所有點，維護出id和blocks數(shù)組信息
讀入所有航線，維護出in數(shù)組，計算所有點的入度后按照拓撲序跑堆d
// 道路是雙向的，航線單向，可能是負數(shù)也可能是正數(shù)
// 并且圖中保證不會存在環(huán)路
// 直接spfa？
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 3e4, M = 2e5;
int h[N], e[M], ne[M], w[M], idx = 1;
int n, p, r, s;
int dis[N]; bool st[N];
int id[N], cnt, in[N];
vector<int> blocks[N];
queue<int> q;
void add(int x, int y, int d)
{
e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}
void dfs(int x)
{
id[x] = cnt;
blocks[cnt].push_back(x);
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (!id[y]) dfs(y);
}
}
void dijkstra(int k)
{
priority_queue<PII, vector<PII>, greater<PII>> hp;
for (auto x : blocks[k]) hp.push({ dis[x], x });
while (hp.size())
{
auto t = hp.top(); hp.pop();
int x = t.second, d = t.first;
if (st[x]) continue;
st[x] = true;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (id[x] != id[y] && -- in[id[y]] == 0) q.push(id[y]);
if (dis[y] > d + w[i])
{
dis[y] = d + w[i];
if (id[x] == id[y]) hp.push( {dis[y], y });
}
}
}
}
void topsort()
{
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
for (int i = 1; i <= cnt; ++ i )
if (!in[i]) q.push(i);
while (q.size())
{
int x = q.front(); q.pop(); // 連通塊id
dijkstra(x);
}
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d%d%d", &n, &r, &p, &s);
int x, y, d;
for (int i = 0; i < r; ++ i )
{
scanf("%d%d%d", &x, &y, &d);
add(x, y, d), add(y, x, d);
}
for (int i = 1; i <= n; ++ i )
{
if (!id[i])
{
cnt ++ ;
dfs(i); // 維護出i所在的連通塊
}
}
for (int i = 0; i < p; ++ i )
{
scanf("%d%d%d", &x, &y, &d);
add(x, y, d);
in[id[y]] ++ ;
}
topsort();
for (int i = 1; i <= n; ++ i )
{
if (dis[i] >= 0x3f3f3f3f / 2) puts("NO PATH");
else printf("%d\n", dis[i]);
}
return 0;
}
341. 最優(yōu)貿(mào)易
341. 最優(yōu)貿(mào)易 - AcWing題庫
狀態(tài)表示：
集合：所有從1~n的路徑，用分界點將這些路徑一分為二
屬性：在分界點之前（包括分界點）買入 - 在分界點（包括分界點）之后能賣出的最大價值，即最大賣出價值 - 最小買入價值
f
(
i
)
f(i)
f(i)表示以i號點為分界點的1~n路徑中，可以賺取的最大價值
狀態(tài)劃分：分界點從1~n，此時劃分的子集不遺漏地組成了整個集合（雖然有重復，但是題目要求最優(yōu)解，重復的情況不影響最優(yōu)解）
如何求路徑中的前半段最小值
d
m
i
n
(
k
)
dmin(k)
dmin(k)？
若與k直接相連的點有t個，那么
d
m
i
n
(
k
)
=
m
i
n
(
d
m
i
n
(
s
1
)
,
d
m
i
n
(
s
2
)
,
.
.
.
d
m
i
n
(
s
t
)
,
w
k
)
dmin(k) = min(dmin(s_1), dmin(s_2), ... dmin(s_t), w_k)
dmin(k)=min(dmin(s1?),dmin(s2?),...dmin(st?),wk?)
走到k的最小值就等于從所有走到與k直接相連的點的最小值以及自己的權(quán)值中的最小值
由于這些狀態(tài)依賴可能存在環(huán)，即當dp推導出的狀態(tài)不是最優(yōu)解，所以這里用最短路求這些狀態(tài)
最短路用dijkstra或者spfa，是否能用dijkstra？由于在最短路問題中，當前點的最短路徑由與之相連的所有點的最短路徑累加上自己的權(quán)值確定，并且權(quán)值只能是正的
根據(jù)這個性質(zhì)，已經(jīng)確定最短路的點在之后的更新中不可能出現(xiàn)更短的路徑
雖然這題的邊權(quán)為正，但是這題的狀態(tài)不是由之前的狀態(tài)累加，而是從之前的狀態(tài)中取min或者max，這就導致dijkstra每次的更新無法求得最優(yōu)解，需要后續(xù)的再次更新，此時的時間復雜度無法保證，這是最關(guān)鍵的，所以不使用dijkstra
那spfa呢？spfa是bellman-ford的優(yōu)化，bellman根據(jù)邊的數(shù)量進行更新，每次更新所有邊
所以bellman能夠保證最短路的邊數(shù)，即時間復雜度是確定的，所以可以使用sfpa文章來源：http://www.zghlxwxcb.cn/news/detail-625960.html
用sfpa跑出dmin和dmax數(shù)組的信息，分別存儲了從1到k的最小值，以及從k到n的最大值
由于從k到n的起點是變化的，但是終點不變，所以這里可以建一張反向圖，以n為起點，更新dmax文章來源地址http://www.zghlxwxcb.cn/news/detail-625960.html
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 2e6;
int w[N];
int hs[N], ht[N], e[M], ne[M], idx;
int dmin[N], dmax[N]; bool st[N];
int n, m;
int q[N];
void spfa(int h[], int dis[], int t)
{
int tt = 0, hh = 0;
if (t == 1)
{
memset(dis, 0x3f, sizeof(dmin));
q[tt ++ ] = 1; st[1] = true;
dis[1] = w[1];
}
else
{
memset(dis, -0x3f, sizeof(dmax));
q[tt ++ ] = n; st[n] = true;
dis[n] = w[n];
}
while (tt != hh)
{
int x = q[hh ++ ];
if (hh == N) hh = 0;
st[x] = false;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if ((t == 1 && dis[y] > min(dis[x], w[y])) || (t == 2 && dis[y] < max(dis[x], w[y])))
{
if (t == 1) dis[y] = min(dis[x], w[y]);
else dis[y] = max(dis[x], w[y]);
if (!st[y])
{
st[y] = true, q[tt ++ ] = y;
if (tt == N) tt = 0;
}
}
}
}
}
void add(int h[], int x, int y)
{
e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}
int main()
{
memset(hs, -1, sizeof(hs));
memset(ht, -1, sizeof(ht));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++ i ) scanf("%d", &w[i]);
int x, y, t;
while ( m -- )
{
scanf("%d%d%d", &x, &y, &t);
add(hs, x, y), add(ht, y, x);
if (t == 2) add(hs, y, x), add(ht, x, y);
}
spfa(hs, dmin, 1);
spfa(ht, dmax, 2);
int res = 0;
for (int i = 1; i <= n; ++ i )
{
res = max(res, dmax[i] - dmin[i]);
}
printf("%d\n", res);
return 0;
}
到了這里，關(guān)于第三章 圖論 No.1單源最短路及其綜合應用的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
