CF360E Levko and Game 题解
swiftc
2021-08-12 16:02:03
$d_1(x)$：从 $s_1$ 到 $x$ 的距离。
$d_2(x)$：从 $s_2$ 到 $x$ 的距离。
我们将一条边 $(a,b)$ 的权值只可能调整到 $l_i$ 或 $r_i$，考虑以下三种情况：
1. 这条边没有被任何人经过
不影响答案。
2. 这条边被 A 经过但没有被 B 经过
因为 B 之前没有选择走这条边，一定有 $d_1(a) < d_2(a)$ ，所以如果在这之后 B 选择走这条边 $d_1(t) = d_1(a)+dis(a,b)+dis(b,t)$ 也一定小于 $d_2(t) = d_2(a) + dis(a,b) + dis(b,t) $，如果 B 不选择走这条边，$d_1(t)$ 减小而 $d_2(t)$ 没有变化。
3. 这条边被 A，B 同时经过
$d_1(t)$ 和 $d_2(t)$ 减小同样的数值。
（这里只考虑调小，调大同理）
那么我们有一种做法，首先把所有边权设为 $r_i$，然后对于每一条边，如果有 $d_1(a) < d_2(a)$，那么将它的边权设为 $l_i$，最后判断 $d_1(t)$ 是否小于 $d_2(t)$，如果不是则所有边权设为 $r_i$ 再来一次，如果有 $d_1(a) \le d_2(a)$，那么将它的边权设为 $l_i$，最后判断$d_1(t)$ 是否小于等于 $d_2(t)$ 即可。
考虑这种做法的正确性，
1. 如果一条边满足 $d_1(a) < d_2(a)$，则之后对边权的改变不会影响这个性质
考虑反证，如果在改变 $(a_2,b_2)$ 后 $d_2(a_1) \le d_1(a_1)$，因为我们只改变了一条边就使 $d_2(a_1)$ 减小了，那么 $(a_2,b_2)$ 一定在 $s_2$ 到 $a_1$ 的最短路上，那么 $d_2(a_1)=d_2(a_2)+dis(a_2,b_2)+dis(a_2,a_1)$ 大于 $d_1(a_1)=d_1(a_2)+dis(a_2,b_2)+dis(a_2,a_1)$，矛盾。
2. 所以在最后所有边权为 $l_i$ 的边都会满足 $d_1(a) < d_2(a)$，而其他的边在任何可能的边权下都会有 $d_1(a) \ge d_2(a)$（即对答案没有正面贡献）
```cpp
// Problem: CF360E Levko and Game
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF360E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define N 100000
#define int long long
using namespace std;
int n, m, k, s1, s2, f, head[N], nxt[N], to[N], cnt, s[N], t[N], l[N], r[N],
v[N], d1[N], d2[N];
int *len[N];
void add(int a, int b, int *l) {
nxt[++cnt] = head[a];
to[cnt] = b;
len[cnt] = l;
head[a] = cnt;
}
struct node {
int x, v;
node(int _x, int _v) : x(_x), v(_v) {}
bool operator<(const node &t) const { return v > t.v; }
};
void dij(int s, int *dis) {
memset(dis, 0x3f, sizeof(int) * (n + 1));
priority_queue<node> p;
dis[s] = 0;
p.emplace(s, 0);
while (!p.empty()) {
node x = p.top();
p.pop();
if (dis[x.x] != x.v) continue;
for (int i = head[x.x]; i; i = nxt[i]) {
if (dis[to[i]] > dis[x.x] + *len[i]) {
dis[to[i]] = dis[x.x] + *len[i];
p.emplace(to[i], dis[to[i]]);
}
}
}
}
bool solve(int d) {
bool flag = false;
do {
flag = false;
dij(s1, d1);
dij(s2, d2);
for (int i = 1; i <= k; i++) {
if (v[i] == r[i] && d1[s[i]] < d2[s[i]] + d) {
v[i] = l[i];
flag = 1;
}
}
} while (flag);
return d1[f] < d2[f] + d;
}
signed main() {
cin >> n >> m >> k;
cin >> s1 >> s2 >> f;
for (int i = 1; i <= m; i++) {
int a, b, l;
cin >> a >> b >> l;
add(a, b, new int(l));
}
for (int i = 1; i <= k; i++) {
cin >> s[i] >> t[i] >> l[i] >> r[i];
v[i] = r[i];
add(s[i], t[i], &v[i]);
}
for (int i = 1; i <= k; i++) {
dij(s1, d1);
dij(s2, d2);
if (d1[s[i]] < d2[s[i]]) {
v[i] = l[i];
}
}
if (solve(0)) {
puts("WIN");
for (int i = 1; i <= k; i++) {
cout << v[i] << " ";
}
return 0;
}
if (solve(1)) {
puts("DRAW");
for (int i = 1; i <= k; i++) {
cout << v[i] << " ";
}
return 0;
}
puts("LOSE");
return 0;
}
```