问题 I: 旅行
传送门：ZWGOJ
题目描述
原题面
乐乐要是开始他的背包旅行，这次共 \(n\) 个城市，编号为 \(1 \sim n\)。乐乐从编号为 \(1\) 的城市出发，前往编号为 \(n\) 的城市。每个城市都有一件物品，重量为 \(w_i\)，价值为 \(v_i\)。乐乐从一个城市到另一个城市，如果背包中的物品重量为 \(a\)，行走距离为 \(b\) 时，花费的体力为 \(a \times b\)，乐乐最多只能背总重量为 \(W\) 的物品。乐乐希望到达 \(n\) 时，背包中的物品价值最大，同时花费的体力最小。\(n\) 个城市之间共 \(m\) 条单向路，且无环，从一个城市出发之后，无法再回到这个城市。
输入要求
第一行 \(3\) 个整数 \(n,\: m,\:W\)。
接下来 \(n\) 行，每行 \(2\) 个整数表示 \(w_i\) 和 \(v_i\)。
接下来 \(m\) 行，每行 \(3\) 个整数 \(x_i,\:y_i,\:z_i\)，无重边，无自环。数据保证 \(1\) 可以到达 \(n\)。
输出要求
输出 \(2\) 个整数，表示最大值价值和获得最大值情况下最小的体力消耗。
样例
1
2
3
4
5
6
7
8
9
10
11
12 | 5 6 10
2 2
1 3
3 5
4 2
2 3
1 2 1
2 4 5
2 5 3
1 3 4
3 4 2
4 5 2
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | 背包容量：10
（X代表装不下背包，该方案被舍弃）
------------------------------------------------------------------
法1：1 → 3 → 4 → 5
选择：1345 134 135 145 345 13 14 15 34 35 45 1 3 4 5
容量：X11 9 7 8 9 5 6 4 7 5 6 2 3 4 2
价值：X12 9 10 7 10 7 4 5 7 8 5 2 5 2 3
体力：X36 36 28 24 20 28 24 16 20 12 8 16 12 8 0
---
体力计算：1: 16; 3: 12; 4: 8; 5: 0
------------------------------------------------------------------
法2：1 → 2 → 5
选择：125 12 15 25 1 2 5
价值：5 3 4 3 2 1 2
体力：11 11 8 3 8 3 0
---
体力计算：1: 8; 2: 3; 5: 0
------------------------------------------------------------------
法3：1 → 2 → 4 → 5
选择：1245 124 125 145 245 12 14 15 24 25 45 1 2 4 5
价值：9 7 5 8 7 3 6 4 5 3 6 2 1 4 2
体力：31 31 23 24 15 23 24 16 15 7 8 16 7 8 0
---
体力计算：1: 16; 2: 7; 4: 8; 5: 0
------------------------------------------------------------------
答案路线：1(不选) → 3(选) → 4(选) → 5(选)
最大价值：10
最小体力：20
|
解法
DAG 图，使用拓扑排序；使用 01 背包完成动态规划状态转移。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79 | #include <bits/stdc++.h>
#define int long long int
using namespace std;
typedef pair<signed, int> pii;
const int MAXn = 8e3 + 9;
const int MAXw = 1e3 + 9;
int w[MAXn], v[MAXn], rd[MAXn];
vector<pii> g[MAXn];
queue<signed> que;
vector<signed> ord;
int dp[MAXn][MAXw], ans[MAXn][MAXw];
bool can[MAXn];
signed main() {
for(int i = 0; i <= MAXn - 3; i ++)
for(int j = 0; j <= MAXw - 3; j ++)
ans[i][j] = LLONG_MAX - 1;
int n, m, W;
scanf("%lld%lld%lld", &n, &m, &W);
for(int i = 1; i <= n; i ++)
scanf("%lld%lld", &w[i], &v[i]);
for(int i = 1, x, y, z; i <= m; i ++) {
scanf("%lld%lld%lld", &x, &y, &z);
g[x].push_back({y, z});
rd[y] ++;
}
// 拓扑排序
for(int i = 1; i <= n; i ++)
if(rd[i] == 0)
que.push(i), ord.push_back(i);
while(!que.empty()) {
signed u = que.front();
que.pop();
for(pii x : g[u]) {
rd[x.first] --;
if(rd[x.first] == 0)
que.push(x.first), ord.push_back(x.first);
}
}
// 01 背包
can[1] = true;
for(int j = 0; j <= W; j ++) {
ans[1][j] = 0;
if(j >= w[1]) dp[1][j] = v[1];
}
int i = 0;
while(i < n && ord[i] != 1) i ++;
for(; i < ord.size(); i ++) {
signed now = ord[i];
if(!can[now]) continue;
for(pii x : g[now]) {
signed nxt = x.first;
int dis = x.second;
can[nxt] = true;
for(int j = W; j >= 0; j --) {
if(j >= w[nxt]) {
if(dp[now][j - w[nxt]] + v[nxt] > dp[nxt][j]) {
dp[nxt][j] = dp[now][j - w[nxt]] + v[nxt];
ans[nxt][j] = ans[now][j - w[nxt]] + dis * (j - w[nxt]);
}
else if(dp[now][j - w[nxt]] + v[nxt] == dp[nxt][j])
ans[nxt][j] = min(ans[nxt][j], ans[now][j - w[nxt]] + dis * (j - w[nxt]));
}
if(dp[now][j] > dp[nxt][j]) {
dp[nxt][j] = dp[now][j];
ans[nxt][j] = ans[now][j] + dis * j;
}
else if(dp[now][j] == dp[nxt][j])
ans[nxt][j] = min(ans[nxt][j], ans[now][j] + dis * j);
}
}
}
int fdp = 0, fans = LLONG_MAX;
for(int j = 0; j <= W; j ++)
if(dp[n][j] > fdp || (dp[n][j] == fdp && ans[n][j] < fans))
fdp = dp[n][j], fans = ans[n][j];
printf("%lld %lld", fdp, fans);
return 0;
}
|
关于无环图
生成无环图
使用以下 python 代码可以生成一张有向无环图。为保证题目有解，生成的图是联通的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | import networkx as nx
import random
def generate_dag(n, m):
G = nx.DiGraph()
nodes = list(range(1, n + 1))
G.add_nodes_from(nodes)
# Step 1: Create a basic connected structure (linear chain)
for i in range(1, n):
G.add_edge(i, i + 1, weight=random.randint(1, 10))
# Step 2: Add remaining edges while keeping the graph acyclic
while len(G.edges) < m:
u, v = random.sample(nodes, 2)
if not G.has_edge(u, v):
G.add_edge(u, v, weight=random.randint(1, 10))
if not nx.is_directed_acyclic_graph(G):
G.remove_edge(u, v)
return G
n = 995
m = 1080
w = 872
G = generate_dag(n, m)
edge_list = list(G.edges(data=False))
random.shuffle(edge_list)
with open('output.txt', 'w') as f:
f.write(f"{n} {m} {w}\n")
for i in range(1, n + 1):
f.write(f"{random.randint(1, 30)} {random.randint(1, 30)}\n")
for u, v in edge_list:
f.write(f"{u} {v} {random.randint(1, 30)}\n")
|
检验无环图
使用 dfs 或 拓扑算法皆可检验一张图是否是无环的。
| 使用 dfs 检验无环性 |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63 | #include <bits/stdc++.h>
using namespace std;
bool dfs(int node, vector<int>& visited, vector<vector<int>>& adj) {
visited[node] = 1;
for (int neighbor : adj[node]) {
if (visited[neighbor] == 1) {
return true;
} else if (visited[neighbor] == 0 && dfs(neighbor, visited, adj)) {
return true;
}
}
visited[node] = 2;
return false;
}
bool hasCycleDFS(int n, vector<pair<int, int>>& edges) {
vector<vector<int>> adj(n + 1);
for (auto& edge : edges) {
adj[edge.first].push_back(edge.second);
}
vector<int> visited(n + 1, 0);
for (int i = 1; i <= n; ++i) {
if (visited[i] == 0 && dfs(i, visited, adj)) {
return true;
}
}
return false;
}
int main() {
freopen("output.txt", "r", stdin);
int n, m, tmp;
cin >> n >> m >> tmp;
for(int i = 1; i <= n; i ++)
cin >> tmp, cin >> tmp;
vector<pair<int, int>> edges(m);
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b >> tmp;
edges[i] = {a, b};
}
if (hasCycleDFS(n, edges)) {
cout << "Graph has a cycle (detected by DFS)." << endl;
} else {
cout << "Graph does not have a cycle (detected by DFS)." << endl;
}
// if (hasCycleTopo(n, edges)) {
// cout << "Graph has a cycle (detected by Topological Sort)." << endl;
// } else {
// cout << "Graph does not have a cycle (detected by Topological Sort)." << endl;
// }
return 0;
}
|
| 使用 拓扑排序 检验无环性 |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66 | #include <bits/stdc++.h>
using namespace std;
bool hasCycleTopo(int n, vector<pair<int, int>>& edges) {
vector<vector<int>> adj(n + 1);
vector<int> inDegree(n + 1, 0);
for (auto& edge : edges) {
adj[edge.first].push_back(edge.second);
inDegree[edge.second]++;
}
queue<int> q;
for (int i = 1; i <= n; ++i) {
if (inDegree[i] == 0) {
q.push(i);
}
}
int count = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
count++;
for (int neighbor : adj[node]) {
if (--inDegree[neighbor] == 0) {
q.push(neighbor);
}
}
}
return count != n;
}
int main() {
freopen("output.txt", "r", stdin);
int n, m, tmp;
cin >> n >> m >> tmp;
for(int i = 1; i <= n; i ++)
cin >> tmp, cin >> tmp;
vector<pair<int, int>> edges(m);
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b >> tmp;
edges[i] = {a, b};
}
// if (hasCycleDFS(n, edges)) {
// cout << "Graph has a cycle (detected by DFS)." << endl;
// } else {
// cout << "Graph does not have a cycle (detected by DFS)." << endl;
// }
if (hasCycleTopo(n, edges)) {
cout << "Graph has a cycle (detected by Topological Sort)." << endl;
} else {
cout << "Graph does not have a cycle (detected by Topological Sort)." << endl;
}
return 0;
}
|