[20220115杂题选讲]Robot

Posted on | In ,

首先建立虚点，然后跑最短路，注意考虑一种特殊情况。

大意

给定 $n$ 个点 $m$ 条边的简单无向图，边有颜色，要求从 $1$ 走到 $n$，但是要求走的每条边 $u\to v$ 都要满足 $u$ 的出边中没有其他与 $(u,v)$ 同色的边。

每条边可以以 $p_i$ 的代价被修改为任意其他的颜色，若想使存在从 $1$ 走到 $n$ 的一个方案，求最小花费。

可能无解。

$n\le 10^5$，$m\le 2\times 10^5$，颜色数 $\le m$，$1\le p_i\le 10^9$，时限 4s。

source: JOI 2021 Final T4 Robot

link: https://loj.ac/p/3471

思路

首先连通就有解，因为可以做到让每条边颜色各不相同。

不难发现如果我们需要走一条本来不能走的边 $u\to v$，有以下两种修改方案：

  1. 修改 $u\to v$ 的颜色为一条完全不同的颜色
  2. 修改与 $u\to v$ 同色的全部 $u$ 的出边为完全不同的颜色

假设这样的情况：$u\to v\to w$，其中两条边都是红色，那么如果在 $u\to v$ 时选择了 1，在 $v\to w$ 选择 2 时还修改 $v\to u$ 就显得很亏。

考虑建虚点。对于结点 $u$，对每种包含在它出边中的颜色 $c$ 另开一个虚点 $\lang u,c\rang$，$u\stackrel{0}\to\lang u,c\rang$，$\lang u,c\rang\stackrel{-pv+\sum\limits{u\stackrel{c}\to w} p_w}\to v$，$v\stackrel 0\to\lang u,c\rang$，$u\stackrel{p_i}\to v$。（$(u,v)$ 颜色为 $c$）

正常来说，第一种修改相当于走第四种边；第二种修改相当于走第一、二种边，而特殊情况相当于走第三、二种边。

直接建图，但是要注意点数是 $O(m)$ 而非 $O(n^2)$ 的，所以可能要用 unordered_map 来做到常规的数组。

有人说 map 更快？简单测试一下：

-O0 -O2
std::map 27128ms 34582ms
std::unordered_map 22148ms 33912ms

代码

Dijkstra 写错就离谱……

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cstdint>
#include <random>
#include <map>

namespace mirai {

constexpr int MAXN = 100005;

class edge {
 public:
  int to, color, cost;
};
std::vector<edge> graph[MAXN];

class edge2 {
 public:
  std::pair<int, int> to;
  long long val;
};
class hash {
 public:
  std::size_t operator()(std::pair<std::int32_t, std::int32_t> const& x) const {
    std::hash<std::int64_t> hash;
    return hash((static_cast<std::int64_t>(x.first) << 32) | x.second);
  }
};
class cmp {
 public:
  bool operator()(std::pair<int, int> const& x, std::pair<int, int> const& y) const {
    return x.first == y.first ? x.second < y.second : x.first < y.first;
  }
};

std::unordered_map<std::pair<int, int>, long long, hash> sum;
std::unordered_map<std::pair<int, int>, std::vector<edge2>, hash> graph2;
std::unordered_map<std::pair<int, int>, bool, hash> vst;
std::unordered_map<std::pair<int, int>, bool, hash> vst2;
std::unordered_map<std::pair<int, int>, long long, hash> dist;

//std::map<std::pair<int, int>, long long, cmp> sum;
//std::map<std::pair<int, int>, std::vector<edge2>, cmp> graph2;
//std::map<std::pair<int, int>, bool, cmp> vst;
//std::map<std::pair<int, int>, bool, cmp> vst2;
//std::map<std::pair<int, int>, long long, cmp> dist;

class cmp2 {
 public:
  bool operator()(std::pair<std::pair<int, int>, long long> const& x, std::pair<std::pair<int, int>, long long> const& y) const {
    return x.second > y.second;
  }
};
std::priority_queue<std::pair<std::pair<int, int>, long long>, std::vector<std::pair<std::pair<int, int>, long long>>, cmp2> que;

int main(int argc, char** argv) {
  #ifdef MIRAI
  std::freopen("data/3471-1-10.in", "r", stdin);
  #endif
  int n, m;
  std::scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    int u, v, color, cost;
    std::scanf("%d%d%d%d", &u, &v, &color, &cost);
    graph[u].push_back({v, color, cost});
    graph[v].push_back({u, color, cost});
  }
  for (int i = 1; i <= n; ++i) {
    for (auto e : graph[i]) {
      sum[{i, e.color}] += e.cost;
    }
  }
  
  int cnt = 0;
  for (int i = 1; i <= n; ++i) {
    for (auto e : graph[i]) {
      graph2[{i, 0}].push_back({{e.to, 0}, e.cost});
      if (!vst[{i, e.color}]) {
        vst[{i, e.color}] = true;
        graph2[{i, 0}].push_back({{i, e.color}, 0});
      }
      graph2[{i, e.color}].push_back({{e.to, 0}, sum[{i, e.color}] - e.cost});
      graph2[{e.to, 0}].push_back({{i, e.color}, 0});
    }
  }
  
//  for (int i = 1; i <= n; ++i) {
//    for (auto e : graph[i]) {
//      std::printf("{%d, %d}: ", i, e.color);
//      for (auto e2 : graph2[{i, e.color}]) {
//        std::printf("{{%d, %d}, %lld} ", e2.to.first, e2.to.second, e2.val);
//      }
//      std::puts("");
//    }
//    std::printf("{%d, 0}: ", i);
//    for (auto e2: graph2[{i, 0}]) {
//      std::printf("{{%d, %d}, %lld} ", e2.to.first, e2.to.second, e2.val);
//    }
//    std::puts("");
//  }
  
  for (int i = 1; i <= n; ++i) {
    for (auto e : graph[i]) {
      dist[{i, e.color}] = 0x3f3f3f3f3f3f3f3fll;
    }
    dist[{i, 0}] = 0x3f3f3f3f3f3f3f3fll;
  }
  dist[{1, 0}] = 0;
  que.push({{1, 0}, 0});
  while (!que.empty()) {
    auto top = que.top().first;
    que.pop();
    if (vst2[top]) {
      continue;
    }
    vst2[top] = true;
    for (auto e : graph2[top]) {
      if (dist[e.to] > dist[top] + e.val) {
        dist[e.to] = dist[top] + e.val;
        if (!vst2[e.to]) {
          que.push({e.to, dist[top] + e.val});
        }
      }
    }
  }
  std::printf("%lld\n", dist[{n, 0}] == 0x3f3f3f3f3f3f3f3fll ? -1 : dist[{n, 0}]);
  
  #ifdef MIRAI
  std::fclose(stdin);
  #endif  
  
  return 0;
}

}

int main(int argc, char** argv) {
  return mirai::main(argc, argv);
}