今天考了一道分层图,本来是一道板题,结果我被误导了,想成了 架设电话线一题,考完写炸了才发现,架设电话线只需要求出第k+1大的长度,只需要满足局部最优==,但是飞行线路要使总和最小,只能用分层图,然后我翻了半天标签,找到了这道题。
link
但是当旁边LH看到之后,他告诉我,这是一道DP。
结果我没看出来。。。
分层图倒是很简单。
Sulotion
step1
首先,他可以在图上到处走动,所以很自然地可以建一张图,所有的边权都是0。
然后这道题只与水晶球的价格有关,所以我们把点权搬到边权上面。
step2
因为他只进行一次买卖,所以有下面两种情况:
假设从\(u\)到\(v\),水晶球在\(u\)的价格为\(w\).
1.买. 建第二层图,连接第一层图 -> 在\(u\)和\(v\)之间建一条边边权为\(-w\)。
2.卖. 建第三层图,连接第二层图 -> 在\(u\)和\(v\)之间建一条边边权为\(w\)。
step3
我们在最后有两种方法走向终点:
不买卖直接走向终点
直接在第一层图的n号节点建立边权为0的有向边接入一个“大终点”
买卖一次后走向终点
在第三层图的n号节点建立边权为0的有向边接入“大终点”
至此,这道题就只需要求一个最长路即可。
Code
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100005 * 3 + 1;
int n, m, a[MAXN];
bool vis[MAXN];
int dis[MAXN];
queue<int> q;
void read(int& x) {
x = 0;
int f = 1;
char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') f = -f;
c = getchar();
}
while (c <= '9' && c >= '0') {
x = x * 10 + c - '0';
c = getchar();
}
x *= f;
}
struct edge {
int v, w;
edge(){}
edge(int V, int W) {
v = V;
w = W;
}
};
vector<edge> G[MAXN];
void AddEdge(int u, int v, int w) {
G[u + n * 0].push_back(edge(v + n * 0, 0));
G[u + n * 1].push_back(edge(v + n * 1, 0));
G[u + n * 2].push_back(edge(v + n * 2, 0));
G[u + n * 0].push_back(edge(v + n * 1, -w));
G[u + n * 1].push_back(edge(v + n * 2, w));
}
void Spfa() {
memset(vis, 0, sizeof(vis));
memset(dis, 0xcf, sizeof(dis));
dis[1] = 0;
vis[1] = 1;
q.push(1);
while (q.size()) {
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].v, w = G[u][i].w;
if (dis[v] < dis[u] + w) {
dis[v] = dis[u] + w;
if (vis[v] == 0) {
vis[v] = 1;
q.push(v);
}
}
}
}
printf ("%d\n", dis[n]);
}
int main() {
read(n);
read(m);
for (int i = 1; i <= n; i++) {
read(a[i]);
}
for (int i = 1, u, v, opt; i <= m; i++) {
read(u), read(v), read(opt);
AddEdge(u, v, a[u]);
if (opt == 2) {
AddEdge(v, u, a[v]);
}
}
G[n].push_back(edge(n * 3 + 1, 0));
G[n * 3].push_back(edge(n * 3 + 1, 0));
n *= 3;
n++;
Spfa();
return 0;
}