所谓分层图,即通过构建一张新图使得一张图有多个维度。一个典型的例子是使一张图复制出一份或多份,并在复制出的不同的层之间根据要求连接某些点。
一个典型的应用就是在不同路径上有
给定一个包含
容易发现在不考虑进行决策的情况下(即
考虑进行决策。对于每一条边,我们都可以有选择按照原有边权走或者按边权为
接下来我们需要考虑限定
显然,对于
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, K, s, t;
struct Edge {
int v, w;
};
vector<Edge> G[N];
int dis[N], vis[N];
void addEdge(int u, int v, int w) {
G[u].push_back(Edge{v, w});
}
void dijkstra(int u) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
struct Node {
int dis, u;
bool operator>(const Node& a) const {
return dis > a.dis;
}
};
priority_queue<Node, vector<Node>, greater<Node>> q;
q.push(Node{0, u});
dis[u] = 0;
while (!q.empty()) {
Node curr = q.top();
q.pop();
int u = curr.u;
if (vis[u]) continue;
vis[u] = 1;
for (auto edge : G[u]) {
int v = edge.v, w = edge.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push(Node{dis[v], v});
}
}
}
}
int main() {
for (int i = 0; i < N; i++) G[i].clear();
scanf("%d%d%d", &n, &m, &K);
scanf("%d%d", &s, &t);
s++, t++;
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
u++, v++;
addEdge(u, v, w);
addEdge(v, u, w);
for (int i = 1; i <= K; i++) {
int uu = i * n + u, vv = i * n + v;
addEdge(uu, vv, w);
addEdge(vv, uu, w);
addEdge((i - 1) * n + u, vv, 0);
addEdge((i - 1) * n + v, uu, 0);
}
}
dijkstra(s);
int ans = 0x3f3f3f3f;
for (int i = 0; i <= K; i++) {
ans = min(ans, dis[i * n + t]);
}
printf("%d\n", ans);
return 0;
}
需要注意的是,在统计答案时我们需要在
给定一个
定义一次决策为将任意一条边
考虑建图。显然可以将决策转化为分层图求解。
对于原图
然后可以考虑求最长路。显然上述做法建出来的图无法保证是 DAG ,故先进行 Tarjan 缩点后重新建带权图,最后使用拓扑排序求最长路。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m;
int dfn[N], low[N], color[N], sccCnt = 0, idx = 0, vis[N];
set<int> scc[N];
stack<int> s;
int dis[N], inDegree[N];
class Graph {
private:
vector<int> G[N];
public:
int inDegree[N];
void addEdge(int u, int v) {
G[u].push_back(v);
inDegree[v]++;
}
vector<int> operator[](int x) {
return G[x];
}
} G, G2;
void tarjan(int u) {
dfn[u] = low[u] = ++idx;
vis[u] = 1;
s.push(u);
for (auto v : G[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (vis[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
sccCnt++;
while (!s.empty()) {
int x = s.top();
s.pop();
scc[sccCnt].insert(x);
color[x] = sccCnt;
vis[x] = 0;
if (u == x) break;
}
}
}
void toposort(int s) {
queue<int> q;
for (int i = 1; i <= sccCnt; i++) {
if (G2.inDegree[i] == 0) q.push(i);
}
dis[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : G2[u]) {
G2.inDegree[v]--;
if (G2.inDegree[v] == 0) {
q.push(v);
}
if (dis[u] >= 0) dis[v] = max(dis[v], dis[u] + (int)scc[v].size());
}
}
}
int main() {
memset(dis, -0x3f, sizeof(dis));
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
G.addEdge(u, v);
G.addEdge(v, u + n);
G.addEdge(u + n, v + n);
}
for (int i = 1; i <= 2 * n; i++) {
if (!dfn[i]) tarjan(i);
}
for (int u = 1; u <= 2 * n; u++) {
for (auto v : G[u]) {
if (color[u] == color[v]) continue;
G2.addEdge(color[u], color[v]);
}
}
toposort(color[1]);
printf("%d\n", max(dis[color[1]], dis[color[1 + n]]));
return 0;
}
分层图是一种实用的建图思想,可以解决多种图上决策问题。实际使用中需要注意层与层之间的联系,必要时可结合 Tarjan 缩点后处理。