Contents
一般最短路
Floyd 传递闭包
可以使用 bitset 优化:
题目大意:
给一个 n 个点的有向图,其连通数指图中可达顶点对个的个数(包括自己和自己)。求图中的连通数
问题分析:
可以直接 Floyd 传递闭包搞。
如果上面做法被卡,可以先用 Tarjan 缩点,然后在 DAG 上 BFS 或者 DFS 找出每个点可以通向的点。这个过程同样可以用 bitset 来优化。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 50;
int n;
string s;
bitset<N> l[N];
void Floyd() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (l[j][i]) {
l[j] |= l[i];
}
}
}
}
int main(int argc, const char * argv[]) {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
cin >> s;
for (int j = 0; j < n; j++) {
l[i][j] = s[j] - '0';
}
l[i][i] = 1;
}
Floyd();
int ans = 0;
for (int i = 0; i < n; i++) {
ans += l[i].count();
}
printf("%d\n", ans);
return 0;
}
Dijkstra
typedef pair<int, int> pii;
#define mp make_pair
int dis[N], vis[N];
priority_queue< pii, vector<pii>, greater<pii> > pq;
void Dijkstra(int rt) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
while (!pq.empty()) pq.pop();
dis[rt] = 0;
pq.push({0, rt});
while (!pq.empty()) {
pii t = pq.top(); pq.pop();
if (vis[t.second]) continue;
vis[t.second] = 1;
for (int i = head[t.second]; i; i = e[i].nex) {
int to = e[i].to;
if (dis[to] > t.first + e[i].w) {
dis[to] = t.first + e[i].w;
pq.push(mp(dis[to], to));
}
}
}
}
例题:2019ICPC银川 H. Delivery Route
题目大意:
给你一幅图,有 x 条无向边和 y 条有向边。其中无向变的权值均为正,有向边的权值可能为负。保证如果从 a_i 到 b_i 有一条有向边,则不存在 b_i 到 a_i 的路径。给你一个出发点,求单源最短路径。
分析:
首先,由于存在负权路径,直接 Dijkstra 显然不可取。考虑使用 spfa,又很容易被卡掉。我们观察题目比起裸的单源最短路径有何区别:将无向图的每个联通块缩成点后,形成了一个拓扑图!
于是我们可以先用 dfs 对所有的联通块染色,按照拓扑排序的顺序,对每个联通块内部用 Dijkstra。如果一条边连向另一个联通块,就更新该点的最短路径(但不加入堆中)。对一个联通块做完 Dijkstra,我们遍历其中所有点,对其连边所指向的联通块度数减 1;遍历到一个新的联通块,我们把所有最短路径不为 INF
的点加入优先队列。
#include <bits/stdc++.h>
using namespace std;
int n, x, y, s;
const int N = 2e5 + 50;
typedef pair<int, int> pii;
#define mp make_pair
int head[N], tot;
struct Edge {
int nex, to, w;
}e[N];
void addedge(int a, int b, int c) {
e[++tot] = {head[a], b, c};
head[a] = tot;
}
void add(int a, int b, int c) {
addedge(a, b, c);
addedge(b, a, c);
}
vector<int> bel[N];
int co[N], cnt; //联通块的颜色、联通块的数量
void dfs(int v, int col) { //dfs给联通块染色
co[v] = col;
bel[col].push_back(v);
for (int i = head[v]; i; i = e[i].nex) {
int to = e[i].to;
if (!co[to]) dfs(to, col);
}
}
int deg[N], dis[N];//每个联通块的入度、单源最短路径
int vis[N];
queue<int> qu;//拓扑排序:入度为0的联通块入队
priority_queue< pii, vector<pii>, greater<pii> > pq;
void Dijkstra(int S) {
memset(dis, 0x3f, sizeof(dis));
dis[S] = 0;
for (int i = 1; i <= cnt; i++) if (!deg[i]) qu.push(i);
while (!qu.empty()) { //topological-sort
int u = qu.front(); qu.pop();
int sz = (int)bel[u].size();
for (int i = 0; i < sz; i++) if (dis[bel[u][i]] < 1e9) {
pq.push(mp(dis[bel[u][i]], bel[u][i]));
}
while (!pq.empty()) { //Dijkstra
int x = pq.top().second; pq.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = head[x]; i; i = e[i].nex) {
int to = e[i].to;
if (co[x] == co[to] && dis[to] > dis[x] + e[i].w) {
dis[to] = dis[x] + e[i].w;
pq.push(mp(dis[to], to));
}
if (co[x] != co[to]) {
dis[to] = min(dis[to], dis[x] + e[i].w);
}
}
}
for (int x = 0; x < sz; x++) {
int y = bel[u][x];
for (int i = head[y]; i; i = e[i].nex) {
int to = e[i].to;
if (co[y] != co[to]) {
deg[co[to]]--;
if (!deg[co[to]]) qu.push(co[to]);
}
}
}
}
}
int main() {
scanf("%d%d%d%d", &n, &x, &y, &s);
for (int i = 1, a, b, c; i <= x; i++) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
for (int i = 1; i <= n; i++) if(!co[i]) dfs(i, ++cnt);
for (int i = 1, a, b, c; i <= y; i++) {
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
deg[co[b]]++;
}
Dijkstra(s);
for(int i = 1; i <=n; i++) {
if (dis[i] > 1e9) puts("NO PATH");
else printf("%d\n", dis[i]);
}
return 0;
}
spfa
queue<int> q;
void spfa(int rt) {
memset(dis, 0x3f, sizeof(dis));
q.push(rt); vis[rt] = 1;
while (!q.empty()) {
int x = q.front();
q.pop(); vis[x] = 0;
for (int i = head[x]; i; i = e[i].nex) {
int to = e[i].to;
if (dis[to] > e[i].w + dis[x]) {
dis[to] = e[i].w + dis[x];
if (!vis[to]) {
vis[to] = 1;
q.push(to);
}
}
}
}
}
Johnson全源最短路
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define mp make_pair
const int INF = 1e9;
const int N = 3e3 + 10;
const int M = 1e4 + 50;
int n, m;
int head[N], tot;
struct Edge {
int nex, to, dis;
}e[M];
void add(int a, int b, int c) {
e[++tot] = (Edge) {head[a], b, c};
head[a] = tot;
}
int d[N], vis[N], tim[N];
queue<int> q;
bool spfa(int u) {
memset(d, 0x3f, sizeof(d));
d[u] = 0; vis[u] = 1;
q.push(u);
while (!q.empty()) {
int v = q.front();
q.pop(); vis[v] = 0;
if (++tim[v] >= n) {
return 0;
}
for (int i = head[v]; i; i = e[i].nex) {
int to = e[i].to;
if (d[to] > d[v] + e[i].dis) {
d[to] = d[v] + e[i].dis;
if (!vis[to]) {
vis[to] = 1;
q.push(to);
}
}
}
}
return 1;
}
int dis[N][N];
priority_queue<pii, vector<pii>, greater<pii> > pq;
void Dijkstra(int u) {
memset(dis[u], 0x3f, sizeof(dis[u]));
memset(vis, 0, sizeof(vis));
while(!pq.empty()) pq.pop();
dis[u][u] = 0;
pq.push(mp(0, u));
while(!pq.empty()) {
pii t = pq.top(); pq.pop();
if(vis[t.second]) continue;
vis[t.second] = 1;
for(int i = head[t.second]; i; i = e[i].nex) {
int to = e[i].to;
if(dis[u][to] > t.first + e[i].dis) {
dis[u][to] = t.first + e[i].dis;
pq.push(mp(dis[u][to], to));
}
}
}
}
int Johnson() {
for (int i = 1; i <= n; i++) {
add(n + 1, i, 0);
}
if (!spfa(n + 1)) {
return -1;
}
for (int u = 1; u <= n; u++) {
for (int i = head[u]; i; i = e[i].nex) {
e[i].dis += d[u] - d[e[i].to];
}
}
for (int i = 1; i <= n; i++) {
Dijkstra(i);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dis[i][j] = dis[i][j] - d[i] + d[j];
}
}
return 1;
}
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1, a, b, c; i <= m; i++) {
cin >> a >> b >> c;
add(a, b, c);
}
if (Johnson() == -1) { // 有负环
cout << "-1\n";
return 0;
}
return 0;
}
变形最短路
同余最短路
题目:P3403 跳楼机
题目大意:
一共有 h 层,开始在第 1 层,有 4 种操作:向上走 x 层,向上走 y 层,向上走 z 层,回到第 1 层。问一共有多少可到达楼层。1\le h\le 2^{63}-1,1\le x,y,z\le 10^5
问题等价于求 x+y+z=k 可能 k 取值的方案数。
分析:
不妨设 x 为最小的数。对 \bmod \ x 构造同余系:设 f[i] 为到达楼层 \bmod \ x\equiv i 的最小楼层,那么 f(i)+x、f(i)+2x 等等都可以到达,这一部分答案为 (h-f[i])/x+1;
考虑如何计算 f[i]。对于每个 i\in[0,x-1],向 (i+y)%x 连一条 y 的边、向 (i+z)%x 连一条 z 的边,跑最短路即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
#define mp make_pair
const int N = 1e5 + 50;
ll h, ans;
int n = 3, a[5], x = N;
int head[N], tot;
struct Edge {
int nex, to, w;
}e[N * 10];
void add(int a, int b, int c) {
e[++tot] = {head[a], b, c};
head[a] = tot;
}
ll dis[N];
int vis[N];
priority_queue< pii, vector<pii>, greater<pii> > pq;
void Dijkstra(int u) {
memset(dis, 0x3f, sizeof(dis));
dis[u] = 1;
memset(vis, 0, sizeof(vis));
while (!pq.empty()) pq.pop();
pq.push({1, u});
while (!pq.empty()) {
pii t = pq.top(); pq.pop();
if (vis[t.second]) continue;
vis[t.second] = 1;
for (int i = head[t.second]; ~i; i = e[i].nex) {
int to = e[i].to;
if(dis[to] > t.first + e[i].w)
{
dis[to] = t.first + e[i].w;
pq.push(mp(dis[to], to));
}
}
}
}
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> h;
for (int i = 1; i <= n; i++) {
cin >> a[i]; x = min(x, a[i]);
}
if (x == 1) {
cout << h << "\n"; return 0;
}
memset(head, -1, sizeof(head));
for (int i = 1; i < x; i++) {
for (int j = 1; j <= n; j++) {
add(i, (i + a[j]) % x, a[j]);
}
}
Dijkstra(1);
for (int i = 0; i < x; i++) {
if (dis[i] <= h) {
ans += (h - dis[i]) / x + 1;
}
}
cout << ans << "\n";
return 0;
}
题目大意:
给 N 个数,求它们最大的不能表示的数。
分析:
仍然构造同余系。对最小的 x 跑同余最短路,每个 dis[i]-x 的最大值即为最大不可能表示的数。
当 N=2 且 \gcd(a,b)=1 时,利用上面做法,答案为 ab-a-b。
概率最短路
题目:P4745 [CERC2017]Gambling Guide
题目大意:
给一张无向图,每次“买票”,从一个点随机到另一个点,可以选择走或不走。给定起点 1 和终点 n,问最小的“买票”期望次数。
分析:
从终点往前合并,满足以合并的点到达终点的期望次数都比未合并的少。
用优先队列维护没有被合并的点到终点的期望次数,记为 now
。开始的时候只有 n 在队列终。每次合并 now
最小的点 p,同时更新所有能到达它的点。对于要更新的点 to,我们分成三种情况:到达已经被合并的点的加权期望步数 tmp
,到达新合并点 p 的加权期望步数 \frac{nd[p].now+1}{degree},到达未合并点并返回的期望步数。我们记录下每个点所连边中,连向已被合并的个数 used
,则每次更新的过程:
nd[to].used++
- 设: t=nd[p].now,x=nd[to].now,有方程:
\begin{aligned}
x&=tmp+\frac{t+1}{degree}+\frac{degree-used}{degree}(x+1)\cr\cr
\iff x&=\frac{degree * tmp+t+1+degree-used}{used}
\end{aligned}
- 更新 to 的
tmp
参数:
tmp=tmp+\frac{t+1}{degree}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 50;
int n, m;
struct Node {
int id;
int deg, used;
double tmp, now;
bool operator < (const Node &x) const {
return now > x.now;
}
}nd[N];
struct Edge {
int nex, to;
}eg[N];
int head[N], tot;
void add(int a, int b) {
eg[++tot] = (Edge){head[a], b};
head[a] = tot;
}
int vis[N];
priority_queue<Node> pq;
void Dijkstra(int S) {
pq.push(nd[S]);
while (!pq.empty()) {
int p = pq.top().id;
pq.pop();
if (vis[p]) continue;
vis[p] = 1;
double t = nd[p].now;
for (int i = head[p]; i; i = eg[i].nex) {
int to = eg[i].to, deg = nd[to].deg;
if (vis[to]) continue;
nd[to].used++;
nd[to].now = (deg * nd[to].tmp + t + 1 + deg - nd[to].used) / nd[to].used;
nd[to].tmp += (t + 1) / deg;
pq.push(nd[to]);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, a, b; i <= m; i++) {
scanf("%d%d", &a, &b);
add(a, b); add(b, a);
nd[a].deg++; nd[b].deg++;
}
for (int i = 1; i <= n; i++) nd[i].id = i;
for (int i = 1; i < n; i++) nd[i].now = 1e15;
Dijkstra(n);
printf("%.10lf\n", nd[1].now);
return 0;
}
分层图最短路
题目大意:
n 个点 m 条边的无向图,每条边有一个花费,其中有 k 次机会可以减免花费。给定起点 s 和终点 t,求最小花费。
分析:
构建分层图,每一层之间均按照正常图相连,在相邻两层之间对应边连一条花费为 0 的边。一共有 k + 1 层。
同时为了计算免费次数用不完的情况,把每层的 t 均相连。对第一层的 s 和最后一层的 t 跑最短路即可。
int main(int argc, const char * argv[]) {
scanf("%d%d%d", &n, &m, &k);
scanf("%d%d", &s, &t);
s++; t++;
for (int i = 1, a, b, c; i <= m; i++) {
scanf("%d%d%d", &a, &b, &c);
a++; b++;
add(a, b, c); add(b, a, c);
for (int i = 1; i <= k; i++) {
int x = (i - 1) * n + a, y = i * n + a;
int u = (i - 1) * n + b, v = i * n + b;
add(x, v, 0); add(u, y, 0);
add(y, v, c); add(v, y, c);
}
}
for (int i = 1; i <= k; i++) {
int x = (i - 1) * n + t, y = i * n + t;
add(x, y, 0);
}
Dijkstra(s);
printf("%d\n", dis[k * n + t]);
return 0;
}
差分约束
题目大意:
给出一组包含 m 个不等式,有 n 个未知数的形如:
\begin{cases}
x_{i_1}-x_{j_1}\leq y_1 \cr x_{i_2}-x_{j_2} \leq y_2 \cr \cdots\cr x_{i_m} – x_{j_m}\leq y_m
\end{cases}
的不等式组,求任意一组满足这个不等式组的解。
分析:
- 从每个 j 向 i 连一条长为 y 的边;新增一个超级源点向每个点连一条长为 0 的边,跑最短路。
如果有负环则无解;否则每个变量的答案为其到超级源点的最短路径。这样输出的答案为各点的最小值。
int main(int argc, const char * argv[]) {
scanf("%d%d", &n, &m);
for (int i = 1, a, b, w; i <= m; i++) {
scanf("%d%d%d", &a, &b, &w);
add(b, a, w);
}
for (int i = 1; i <= n; i++) {
add(n + 1, i, 0);
}
if (!spfa(n + 1)) puts("NO");
else for (int i = 1; i <= n; ++i) {
printf("%d%c", dis[i], i == n ? '\n' : ' ');
}
return 0;
}
- 从每个 i 向 j 连一条长为 -y 的边;新增一个超级源点向每个点连一条长为 0 的边,跑最长路。
如果有正环则无解;否则每个变量的答案为其到超级源点的最短路径。这样输出的答案为各点的最大值。
注意写最长路时,spfa
中的dis
要赋初值 -1,小于号变大于号即可。