C++ Library for Competitive Programming
#include "emthrm/graph/girth_in_undirected_graph.hpp"
グラフに対する最小閉路長である。
$O(\lvert V \rvert (\lvert V \rvert + \lvert E \rvert) \log{\lvert V \rvert})$
名前 | 戻り値 | 要件 |
---|---|---|
template <typename CostType> CostType girth_in_directed_graph(const std::vector<std::vector<Edge<CostType>>>& graph, const CostType inf = std::numeric_limits<CostType>::max());
|
有向グラフ $\mathrm{graph}$ の内周。ただし存在しないときは $\infty$ を返す。 | 辺の重みは自然数である。 |
名前 | 戻り値 | 要件 |
---|---|---|
template <typename CostType> CostType girth_in_undirected_graph(const int n, const std::vector<Edge<CostType>>& edges, const CostType inf = std::numeric_limits<CostType>::max());
|
頂点数 $n$、辺集合 $\mathrm{edges}$ である無向グラフの内周。ただし存在しないときは $\infty$ を返す。 | 辺の重みは自然数である。 |
https://yukicoder.me/submissions/595363
#ifndef EMTHRM_GRAPH_GIRTH_IN_UNDIRECTED_GRAPH_HPP_
#define EMTHRM_GRAPH_GIRTH_IN_UNDIRECTED_GRAPH_HPP_
#include <algorithm>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
#include "emthrm/graph/edge.hpp"
namespace emthrm {
template <typename CostType>
CostType girth_in_undirected_graph(
const int n, const std::vector<Edge<CostType>>& edges,
const CostType inf = std::numeric_limits<CostType>::max()) {
const int m = edges.size();
std::vector<std::vector<int>> graph(n);
for (int i = 0; i < m; ++i) {
graph[edges[i].src].emplace_back(i);
graph[edges[i].dst].emplace_back(i);
}
std::vector<bool> is_used(m, false);
std::vector<int> label(n), prev(n);
std::vector<CostType> dist(n);
std::priority_queue<std::pair<CostType, int>,
std::vector<std::pair<CostType, int>>,
std::greater<std::pair<CostType, int>>> que;
CostType res = inf;
for (int root = 0; root < n; ++root) {
std::fill(is_used.begin(), is_used.end(), false);
std::fill(label.begin(), label.end(), -2);
label[root] = -1;
std::fill(prev.begin(), prev.end(), -1);
std::fill(dist.begin(), dist.end(), inf);
dist[root] = 0;
que.emplace(0, root);
while (!que.empty()) {
const auto [d, ver] = que.top();
que.pop();
if (d > dist[ver]) continue;
for (const int id : graph[ver]) {
const int dst = (edges[id].src == ver ? edges[id].dst : edges[id].src);
const CostType nxt = dist[ver] + edges[id].cost;
if (nxt < dist[dst]) {
dist[dst] = nxt;
label[dst] = (label[ver] == -1 ? dst : label[ver]);
if (prev[dst] != -1) is_used[dst] = true;
is_used[id] = true;
que.emplace(nxt, dst);
}
}
}
for (int i = 0; i < m; ++i) {
const int src = edges[i].src, dst = edges[i].dst;
if (!is_used[i] && label[src] != -2 && label[dst] != -2) {
if (label[src] != label[dst]) {
res = std::min(res, dist[src] + dist[dst] + edges[i].cost);
} else if (label[src] == -1) {
res = std::min(res, edges[i].cost);
}
}
}
}
return res;
}
} // namespace emthrm
#endif // EMTHRM_GRAPH_GIRTH_IN_UNDIRECTED_GRAPH_HPP_
#line 1 "include/emthrm/graph/girth_in_undirected_graph.hpp"
#include <algorithm>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template <typename CostType>
struct Edge {
CostType cost;
int src, dst;
explicit Edge(const int src, const int dst, const CostType cost = 0)
: cost(cost), src(src), dst(dst) {}
auto operator<=>(const Edge& x) const = default;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 12 "include/emthrm/graph/girth_in_undirected_graph.hpp"
namespace emthrm {
template <typename CostType>
CostType girth_in_undirected_graph(
const int n, const std::vector<Edge<CostType>>& edges,
const CostType inf = std::numeric_limits<CostType>::max()) {
const int m = edges.size();
std::vector<std::vector<int>> graph(n);
for (int i = 0; i < m; ++i) {
graph[edges[i].src].emplace_back(i);
graph[edges[i].dst].emplace_back(i);
}
std::vector<bool> is_used(m, false);
std::vector<int> label(n), prev(n);
std::vector<CostType> dist(n);
std::priority_queue<std::pair<CostType, int>,
std::vector<std::pair<CostType, int>>,
std::greater<std::pair<CostType, int>>> que;
CostType res = inf;
for (int root = 0; root < n; ++root) {
std::fill(is_used.begin(), is_used.end(), false);
std::fill(label.begin(), label.end(), -2);
label[root] = -1;
std::fill(prev.begin(), prev.end(), -1);
std::fill(dist.begin(), dist.end(), inf);
dist[root] = 0;
que.emplace(0, root);
while (!que.empty()) {
const auto [d, ver] = que.top();
que.pop();
if (d > dist[ver]) continue;
for (const int id : graph[ver]) {
const int dst = (edges[id].src == ver ? edges[id].dst : edges[id].src);
const CostType nxt = dist[ver] + edges[id].cost;
if (nxt < dist[dst]) {
dist[dst] = nxt;
label[dst] = (label[ver] == -1 ? dst : label[ver]);
if (prev[dst] != -1) is_used[dst] = true;
is_used[id] = true;
que.emplace(nxt, dst);
}
}
}
for (int i = 0; i < m; ++i) {
const int src = edges[i].src, dst = edges[i].dst;
if (!is_used[i] && label[src] != -2 && label[dst] != -2) {
if (label[src] != label[dst]) {
res = std::min(res, dist[src] + dist[dst] + edges[i].cost);
} else if (label[src] == -1) {
res = std::min(res, edges[i].cost);
}
}
}
}
return res;
}
} // namespace emthrm