图论——单源最短路的综合应用
acwing1135.新年好
本题要求的不是单源点最短路，而是从起点开始，走过 a , b , c , d , e a,b,c,d,e a,b,c,d,e五个点的最短距离。
考虑枚举遍历从1开始走遍 a , b , c , d , e a,b,c,d,e a,b,c,d,e点的顺序，方案数为 5 ! 5! 5!,每一个方案都要走过五条路径，例如方案 1 − b − a − e − d − c 1-b-a-e-d-c 1−b−a−e−d−c要走过路径 ( 1 , b ) , ( b , a ) , ( a , e ) , ( e , d ) , ( d , c ) (1,b),(b,a),(a,e),(e,d),(d,c) (1,b),(b,a),(a,e),(e,d),(d,c)。考虑对于每一个方案，都做六遍dijkstra，每次求出来从 1 , a , b , c , d , e 1,a,b,c,d,e 1,a,b,c,d,e中一个点到其他点的最短距离，对于该方案所求的结果就是5个点对之间最短路径的和，这样时间复杂度就是 O ( 6 ! m l o g m ) O(6!mlogm) O(6!mlogm)。考虑先求出从这六个点出发到其他点的最短路径，在枚举所有方案，这样就起到了一个预处理的左右，时间复杂度为 O ( 6 m l o g m + 5 ! ) O(6mlogm+5!) O(6mlogm+5!)。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 50010, M = 1e5 * 2 + 10;
int dist[10][N];
bool st[N];
int h[N], e[M], ne[M], w[M];
int tot;
int source[10];
int n, m;
void add(int a, int b, int c)
{
e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
void dijkstra(int start, int dist[])
{
memset(dist, 0x3f, N * 4);
memset(st, 0, sizeof st);
dist[start] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({dist[start], start});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = 1;
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
return ;
}
int dfs(int u, int last, int val)
{
if (u == 6) return val;
int res = 0x3f3f3f3f;
for (int i = 2; i <= 6; i ++ )
{
int j = source[i];
if (st[i]) continue;
st[i] = 1;
res = min(res, dfs(u + 1, i, val + dist[last][j]));
st[i] = 0;
}
return res;
}
int main()
{
cin >> n >> m;
for (int i = 2; i <= 6; i ++ )
cin >> source[i];
source[1] = 1;
memset(h, -1, sizeof h);
for (int i = 1; i <= m; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
for (int i = 1; i <= 6; i ++ )
dijkstra(source[i], dist[i]);
memset(st, 0, sizeof st);
printf("%d\n", dfs(1, 1, 0));
return 0;
}
acwing340.通信线路
从1号节点到n号节点之间有若干条路径，本题是要在所有路径里找第
k
+
1
k+1
k+1大电缆的最小值，因此可以考虑使用二分来做。
可以用二分的情况是所求的答案在某个分界点，具有某个性质，在这个分界点的一边满足这个性质，另一边不满足。
1.对于答案x，需要满足的性质就是从1走到n需要经过大于x的边数小于等于k，作为分界点，此时大于x的边数应该等于k。
2.对于答案右边的区间，x变大了，大于x的边数就会减小，即大于x的边数小于k，同样满足性质；
2.对于答案左边的区间，x变小了，大于x的边数就会增加，即大于x的边数大于k，不满足性质。
接下来需要判断答案x是否满足上面性质。我们把边权大于x的边权置为1，小于等于x的边权置为0，这样一来图就是一个只有0，1边权的图，我们可以求出一条从1到n的最短路径，如果路径长度 ≤ k \leq k ≤k，则说明x可行。
答案区间为 [ 0 , 1 e 6 + 1 ] [0,1e6+1] [0,1e6+1]，取到0则说明存在长度 ≤ k \leq k ≤k的路径，取到 1 e 6 + 1 1e6+1 1e6+1则说明不存在通路。
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
const int N = 1010, M = 200010;
int h[N], e[M], ne[M], w[M];
int tot;
int dist[N];
bool st[N];
int n, p, k;
void add (int a, int b, int c)
{
e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
bool check(int x)
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
dist[1] = 0;
deque<int> q;
q.push_back(1);
while (q.size())
{
int t = q.front();
q.pop_front();
if (st[t]) continue;
st[t] = 1;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i], val = w[i] > x;
if (dist[j] > dist[t] + val)
{
dist[j] = dist[t] + val;
if (!val) q.push_front(j);
else q.push_back(j);
}
}
}
return dist[n] <= k;
}
int main()
{
cin >> n >> p >> k;
memset(h, -1, sizeof h);
while (p -- )
{
int a, b, c;
cin >> a >> b >> c;
add (a, b, c), add(b, a, c);
}
int l = 0, r = 1e6 + 1;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (r == 1e6 + 1) r = -1;
cout << r;
return 0;
}
acwing342.道路与航线
本题中存在两种路线：
一种是道路，双向，边权非负。
一种是航线，单向，边权可正可负。同时保证保证如果有一条航线可以从
A
i
A_i
Ai到
B
i
B_i
Bi，那么保证不可能通过一些道路和航线从
B
i
B_i
Bi回到
A
i
A_i
Ai。
因为含有负边权，不能使用dijkstra，同时一般的spfa又会被卡，考虑把本题抽象为以下模型：
每一个大圆为一个连通块，大圆内的小圆(城镇)之间可以通过道路相互到达，其中深色小圆为起点，一个大圆可以通过单向的航线到达另一个大圆，大圆之间存在拓扑序。
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
const int N = 25010, M = 1500010;
int id[N];
int h[N], e[M], ne[M], w[M], tot;
vector<int> block[N];
queue<int> q;
int dist[N];
bool st[N];
int pid;
int din[N];
int n, r, p, s;
void add(int a, int b, int c)
{
e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
void dfs(int u, int pid)
{
id[u] = pid;
block[pid].push_back(u);
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (id[j]) continue;
dfs(j, pid);
}
return ;
}
void dijkstra(int x)
{
priority_queue<PII, vector<PII>, greater<PII>> heap;
for (auto i : block[x])
heap.push({dist[i], i});
while (heap.size())
{
auto t = heap.top();
int ver = t.second, distance = t.first;
heap.pop();
if (st[ver]) continue;
st[ver] = 1;
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
if (id[j] == id[ver]) heap.push({dist[j], j});
}
if (id[j] != id[ver] && (-- din[id[j]]) == 0) q.push(id[j]);
}
}
return ;
}
void topsort()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
for (int i = 1; i <= pid; i ++ )
if (din[i] == 0) q.push(i);
while (q.size())
{
int t = q.front();
dijkstra(t);
q.pop();
}
return ;
}
int main()
{
cin >> n >> r >> p >> s;
memset(h, -1, sizeof h);
while (r -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
for (int i = 1; i <= n; i ++ )
{
if (id[i]) continue;
dfs(i, ++ pid);
}
while (p -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
din[id[b]] ++ ;
}
topsort();
for (int i = 1; i <= n; i ++ )
{
if (dist[i] > 0x3f3f3f3f / 2) puts("NO PATH");
else cout << dist[i] << endl;
}
return 0;
}
acwing341.最优贸易
先求出：
从1走到 i的过程中，买入水晶球的最低价格
d
m
i
n
[
i
]
dmin[i]
dmin[i]；
从 i走到n的过程中，卖出水晶球的最高价格
d
m
a
x
[
i
]
dmax[i]
dmax[i]；
然后枚举每个城市作为买卖的中间城市，求出 dmax[i] - dmin[i] 的最大值即可。
求
d
m
i
n
[
i
]
dmin[i]
dmin[i] 和
d
m
a
x
[
i
]
dmax[i]
dmax[i] 时，由于不是拓扑图，状态的更新可能存在环，因此不能使用动态规划，只能使用求最短路的方式。
另外，我们考虑能否使用 dijkstra 算法，如果当前 dmin[i] 最小的点是 5，那么有可能存在边
5
−
>
6
,
6
−
>
7
,
7
−
>
5
5-> 6, 6-> 7, 7-> 5
5−>6,6−>7,7−>5，假设当前
d
m
i
n
[
5
]
=
10
dmin[5] = 10
dmin[5]=10，则有可能存在 6 的价格是11， 但 7 的价格是3，那么
d
m
i
n
[
5
]
dmin[5]
dmin[5] 的值就应该被更新成3，因此当前最小值也不一定是最终最小值，所以dijkstra算法并不适用，我们只能采用 spfa 算法。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = 2000010;
int h[N], rh[N], e[M], ne[M];
int val[N];
int tot;
int q[N];
int dist[N];
bool st[N];
int n, m;
int dmin[N], dmax[N];
void add(int h[], int a, int b)
{
e[tot] = b, ne[tot] = h[a], h[a] = tot ++ ;
}
void spfa(int d[], int start, int h[], bool flag)
{
memset(st, 0, sizeof st);
if (!flag) memset(d, 0x3f, sizeof dmin);
d[start] = val[start];
int hh = 0, tt = 1;
q[0] = start;
st[start] = 1;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = 0;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if ((!flag && d[j] > min(d[t], val[j])) || (flag && d[j] < max(d[t], val[j])))
{
if (!flag) d[j] = min(d[t], val[j]);
else d[j] = max(d[t], val[j]);
if (!st[j])
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = 1;
}
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
cin >> val[i];
memset(h, -1, sizeof h);
memset(rh, -1, sizeof rh);
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
add (h, a, b), add(rh, b, a);
if (c == 2) add(h, b, a), add(rh, a, b);
}
spfa(dmin, 1, h, 0);
spfa(dmax, n, rh, 1);
int res = 0;
for (int i = 1; i <= n; i ++ )
res = max(res, dmax[i] - dmin[i]);
cout << res;
return 0;
}