CF1842D Tenzing and His Animal Friends
该博客的主要内容是关于解决一个图论问题，使用Dijkstra算法计算出聚会的最大总时间，并给出相应的聚会方案。
题目大意
Tenzing有 $n$ 个朋友，编号为 $1$ 至 $n$ ，每次举办聚会可以邀请其中的一些朋友参加，且朋友 $1$ 必须参加，朋友 $n$ 必须不参加。另有 $m$ 条限制，每条限制包含 $u,v,w$ ，表示朋友 $u$ 和朋友 $v$ 中只有一个在聚会中的总时间不超过 $w$ 。
问聚会总时间的最大值，和相应的聚会方案(聚会的总次数，每次聚会的参加情况和每次聚会的时长)。
思路
先构造出图论模型，注意到朋友 $n$ 每次聚会都不参加，则不难发现 $n$ 的相邻节点 $m$ 的参会总时长必须不超过 $w_{mn}$ ，由此又可以推出，对于每个点 $i$ ，它的参会总时长必须不超过它到点 $n$ 的距离。又因为点 $1$ 必须每次都参会，因此最大的聚会总时间即为点 $1$ 到点 $n$ 的最短路。显然，如果 $1$ 与 $n$ 不相连，说明最大聚会总时间没有上限。
下面再考虑如何构造出聚会方案。设存在两个集合 $S,T$ ，集合 $S$ 中为还能参加聚会的点，集合 $T$ 中为不能再参加聚会的点。最初 $T$ 中仅有 $n$ 一个元素。联系到上述每个点最大参会总时长的得出方式，我们每次从 $S$ 中选择一个参会时间上限最短的点 $x$ ，让 $S$ 中的所有点都参加一次聚会，时长为 $x$ 的参会时间上限。一直这样进行下去，直到点 $1$ 不在 $S$ 当中。
不难发现这个思路与 $dijkstra$ 算法存在共通之处，我们进行一次使用dijkstra算法求 $n$ 到 $1$ 的最短路即可。在代码实现的过程中发现了自己dijkstra写的不熟的问题。
代码
xxxxxxxxxx void solve() { int n, m, r; cin » n » m » r; bool dp[n + 10][m + 10][r + 10] = {0}, b[n + 10][m + 10][r + 10]; mem(dp, 0); mem(b, 1); rep(j, 0, r - 1) { int t, d, co; cin » t » d » co; if (d == 1) { rep(i, 0, m) { if (t - co - i >= 0 && t - co - i <= r) b[co][i][t - co - i] = 0; } } else if (d == 2) { rep(i, 0, n) { if (t - co - i >= 0 && t - co - i <= r) b[i][co][t - co - i] = 0; } } } dp[0][0][0] = 1; rep(i, 0, n) rep(j, 0, m) rep(k, 0, r) { if (i > 0) dp[i][j][k] |= dp[i - 1][j][k]; if (j > 0) dp[i][j][k] |= dp[i][j - 1][k]; if (k > 0) dp[i][j][k] |= dp[i][j][k - 1]; dp[i][j][k] &= b[i][j][k]; } rep(i, 0, r) { if (dp[n][m][i]) { cout « n + m + i « endl; return; } } cout « “-1\n”; return;}cpp
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
struct Node {
int val;
vector<int> nex, w;
} g[110];
struct Dist {
int poi, dist;
};
struct Game {
int par[110], t;
};
bool operator>(const Dist x, const Dist y) { return x.dist > y.dist; }
priority_queue<Dist, vector<Dist>, greater<Dist>> q;
int n, m, fi[110], vis[110], dist[110] = {INF}, t = 0;
vector<Game> ans;
int find(int x) { return x == fi[x] ? x : fi[x] = find(fi[x]); }
void build(int u, int v, int w) {
g[u].nex.pb(v);
g[u].w.pb(w);
fi[find(u)] = find(v);
}
signed main() {
ios;
cin >> n >> m;
rep(i, 1, n) { fi[i] = i; }
rep(i, 0, m - 1) {
int u, v, w;
cin >> u >> v >> w;
build(u, v, w);
build(v, u, w);
}
if (find(1) != find(n))
cout << "inf\n";
else {
mem(dist, 0x3f3f3f3f);
int curr = n;
dist[n] = 0;
q.push({n, 0});
while (!q.empty()) {
curr = q.top().poi;
q.pop();
if (vis[curr])
continue;
vis[curr] = 1;
rep(i, 0, (int)g[curr].nex.size() - 1) {
int v = g[curr].nex[i], cost = g[curr].w[i];
if (!vis[v] && dist[v] > dist[curr] + cost) {
dist[v] = dist[curr] + cost;
q.push({v, dist[v]});
}
}
}
cout << dist[1] << " ";
while (dist[1] != 0) {
int minn = INF;
rep(i, 1, n) {
if (dist[i] > 0 && dist[i] < minn)
minn = dist[i];
}
Game a;
rep(i, 1, n) { a.par[i] = dist[i] > 0; }
a.t = minn;
ans.pb(a);
rep(i, 1, n) { dist[i] -= minn; }
}
cout << ans.size() << endl;
for (auto it : ans) {
rep(i, 1, n) { cout << it.par[i]; }
cout << " " << it.t << endl;
}
}
return 0;
}