E - Bichromization
問題
$n$ 頂点 $m$ 辺の無向単純連結グラフが与えられ，頂点 $v$ には整数 $d_v$ が割り付けられている．
可能であれば，以下を満たすように各頂点を白か黒で塗り，各辺に $1$ 以上 $10^9$ 以下の距離を割り付けよ．
- 白および黒に塗られた頂点がそれぞれ少なくとも 1 つ存在する．
- 各頂点 $v$ について， $v$ から $v$ と異なる色の頂点への最短距離は $d_v$ ．
制約
- $2 \leq n \leq 10^5$
- $1 \leq m \leq 2 \cdot 10^5$
- $1 \leq d_i \leq 10^9$
考察
割り付けが不可能な必要十分条件は，「ある $v$ が存在して， $v$ と隣接する任意の $u$ について $d_v \lt d_u$ 」である．
十分性を背理法で示す．このときある頂点 $w$ に対して $v$ から $w$ へ距離 $d_v$ のパスが存在する．このパスは必ず $v$ と隣接するある頂点 $u$ を通るが，
- $w = u$ なら $d_v \leq d_v$ より矛盾．
- $v$ と $u$ が異なる色なら $vu$ 間距離が $vw$ 間距離より短くなり矛盾．
- 同じ色なら $uw$ 間距離が $vw$ 間距離より短くなり矛盾．
ということで，どうしても矛盾が発生する．よって示された．
必要性は対偶を示す，つまり満たされないときに実際に割り付けを構築すればよい．基本方針は「最短距離の実現に十分な全域森を作り，二部グラフになるよう頂点を彩色する」というもの．
最初辺集合 $S$ は空とする．
$v$ を順に見ていく．まず $v$ と接続する距離 $d_v$ なる辺が $S$ に存在すれば，既に条件は満たされているのでスルー(こうしないと森にならない)．
そうでないとき， $v$ と隣接する頂点 $u$ が存在して $d_u \leq d_v$ となる．そこで $S$ に辺 $uv$ を追加し，辺 $uv$ の距離を $d_v$ と定める．
これにより全域森をなす辺集合 $S$ が得られる．
任意の $uv \in S$ に対して，その距離を $d$ とすると $d = \min (d_u, d_v)$ が成り立つ．よって $d_u \leq d_v$ としたとき， $u, v$ を相異なる色で塗れば，パス $uv$ が $u$ からの距離 $d_u$ のパスとなり，かつ辺 $uv$ は $v$ からの最短距離に支障を来さない．
よってこの全域森および彩色は条件を満たす．後は選ばれなかった辺に距離 $10^9$ を割り付ければ，これらは無視されるので条件を満たす割り付けが構成できた．
実装例
大分面倒な実装方針を選んでしまった．
提出 #9591439 - キーエンス プログラミング コンテスト 2020
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
template <class Cost = int>
struct Edge { ... };
template <class Cost = int>
using Edges = std::vector<Edge<Cost>>;
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> ds(n);
for (int i = 0; i < n; ++i) {
auto& d = ds[i];
std::cin >> d;
}
// 辺集合，各頂点に接続する辺番号
Edges<int> es(m);
std::vector<std::vector<int>> graph(n);
for (int i = 0; i < m; ++i) {
auto& e = es[i];
std::cin >> e.src >> e.dst;
--e.src, --e.dst;
e.cost = 1e9;
graph[e.src].push_back(i);
graph[e.dst].push_back(i);
}
std::vector<bool> used(n, false);
std::vector<std::vector<int>> forest(n);
for (int v = 0; v < n; ++v) {
if (used[v]) continue;
// d_u <= d_vなる辺uvを探す
int eid = -1;
for (int i : graph[v]) {
const auto& e = es[i];
int u = e.src;
if (u == v) u = e.dst;
if (ds[u] <= ds[v]) {
eid = i;
break;
}
}
if (eid < 0) {
std::cout << -1 << std::endl;
return;
}
// 辺を森に追加
auto& e = es[eid];
int u = e.src;
if (u == v) u = e.dst;
e.cost = ds[v];
forest[v].push_back(u);
forest[u].push_back(v);
used[v] = true;
if (ds[u] == ds[v]) used[u] = true;
// uの条件も満たされる
}
// BFSで彩色
std::vector<int> cs(n, -1);
for (int r = 0; r < n; ++r) {
if (cs[r] >= 0) continue;
std::queue<int> que;
que.push(r);
cs[r] = 0;
while (!que.empty()) {
int v = que.front();
que.pop();
for (int u : forest[v]) {
if (cs[u] >= 0) continue;
cs[u] = 1 - cs[v];
que.push(u);
}
}
}
for (auto c : cs) std::cout << "BW"[c];
std::cout << std::endl;
for (const auto& e : es) std::cout << e.cost << std::endl;
}
|