library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub yuruhi/library

:heavy_check_mark: test/ChinesePostman.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_2_B"
#include "./../Graph/ChinesePostman.cpp"
#include <iostream>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int n, m;
	cin >> n >> m;
	Graph g(n);
	for (int i = 0; i < m; ++i) {
		int s, t;
		Weight d;
		cin >> s >> t >> d;
		g[s].emplace_back(t, d);
		g[t].emplace_back(s, d);
	}
	cout << ChinesePostman(g) << '\n';
}
#line 1 "test/ChinesePostman.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_2_B"
#line 2 "Graph/GraphTemplate.cpp"
#include <vector>
#include <utility>
#include <iostream>
#include <limits>

using Weight = long long;
constexpr Weight INF = std::numeric_limits<Weight>::max();
struct Edge {
	int to;
	Weight cost;
	Edge() : to(-1), cost(-1) {}
	Edge(int _to, Weight _cost = 1) : to(_to), cost(_cost) {}
	friend bool operator<(const Edge& e1, const Edge& e2) {
		return e1.cost < e2.cost;
	}
	friend bool operator>(const Edge& e1, const Edge& e2) {
		return e1.cost > e2.cost;
	}
	friend std::ostream& operator<<(std::ostream& os, const Edge& e) {
		return os << "->" << e.to << '(' << e.cost << ')';
	}
};
using UnWeightedGraph = std::vector<std::vector<int>>;
using Graph = std::vector<std::vector<Edge>>;
struct Edge2 {
	int from, to;
	Weight cost;
	Edge2() : from(-1), to(-1), cost(0) {}
	Edge2(int _from, int _to, Weight _cost) : from(_from), to(_to), cost(_cost) {}
	friend bool operator<(const Edge2& e1, const Edge2& e2) {
		return e1.cost < e2.cost;
	}
	friend bool operator>(const Edge2& e1, const Edge2& e2) {
		return e1.cost > e2.cost;
	}
	friend std::ostream& operator<<(std::ostream& os, const Edge2& e) {
		return os << e.from << "->" << e.to << '(' << e.cost << ')';
	}
};
using UnWeightedEdges = std::vector<std::pair<int, int>>;
using Edges = std::vector<Edge2>;
using Matrix = std::vector<std::vector<Weight>>;

auto add_edge(UnWeightedGraph& graph, int v, int u) {
	graph[v].push_back(u);
	graph[u].push_back(v);
}
auto add_edge(Graph& graph, int v, int u, Weight cost) {
	graph[v].emplace_back(u, cost);
	graph[u].emplace_back(v, cost);
}
auto to_graph(const UnWeightedGraph& graph, Weight cost = 1) {
	Graph result(graph.size());
	for (std::size_t i = 0; i < graph.size(); ++i) {
		for (int v : graph[i]) {
			result[i].emplace_back(v, cost);
		}
	}
	return result;
}
auto to_unweighted_graph(const Graph& graph) {
	UnWeightedGraph result(graph.size());
	for (std::size_t i = 0; i < graph.size(); ++i) {
		for (auto [v, cost] : graph[i]) {
			result[i].push_back(v);
		}
	}
	return result;
}
auto to_edges(const UnWeightedGraph& graph, bool unique = false) {
	std::vector<std::pair<int, int>> edges;
	for (std::size_t i = 0; i < graph.size(); ++i) {
		for (int v : graph[i]) {
			if (!unique || static_cast<int>(i) < v) edges.emplace_back(i, v);
		}
	}
	return edges;
}
auto to_edges(const Graph& graph) {
	Edges edges;
	for (std::size_t i = 0; i < graph.size(); ++i) {
		for (auto [v, cost] : graph[i]) {
			edges.emplace_back(i, v, cost);
		}
	}
	return edges;
}
#line 4 "Graph/Dijkstra.cpp"
#include <queue>
#include <functional>
#include <cassert>

std::vector<Weight> Dijkstra(const Graph& graph, int s) {
	assert(0 <= s && s <= static_cast<int>(graph.size()));
	std::vector<Weight> dist(graph.size(), INF);
	dist[s] = 0;
	std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq;
	pq.emplace(s, 0);
	while (!pq.empty()) {
		Edge p = pq.top();
		pq.pop();
		int v = p.to;
		if (dist[v] < p.cost) continue;
		for (auto e : graph[v]) {
			if (dist[e.to] > dist[v] + e.cost) {
				dist[e.to] = dist[v] + e.cost;
				pq.emplace(e.to, dist[e.to]);
			}
		}
	}
	return dist;
}
Weight Dijkstra(const Graph& graph, int s, int t) {
	assert(0 <= s && s <= static_cast<int>(graph.size()));
	assert(0 <= t && t <= static_cast<int>(graph.size()));
	std::vector<Weight> dist(graph.size(), INF);
	dist[s] = 0;
	std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq;
	pq.emplace(s, 0);
	while (!pq.empty()) {
		Edge p = pq.top();
		pq.pop();
		int v = p.to;
		if (v == t) return dist[t];
		if (dist[v] < p.cost) continue;
		for (auto e : graph[v]) {
			if (dist[e.to] > dist[v] + e.cost) {
				dist[e.to] = dist[v] + e.cost;
				pq.emplace(e.to, dist[e.to]);
			}
		}
	}
	return dist[t];
}
#line 4 "Graph/ChinesePostman.cpp"
#include <algorithm>

Weight ChinesePostman(const Graph& graph) {
	std::size_t n = graph.size();
	Weight sum = 0;
	std::vector<int> odds;
	for (std::size_t v = 0; v < n; ++v) {
		for (const auto& e : graph[v]) sum += e.cost;
		if (graph[v].size() % 2 == 1) odds.push_back(v);
	}
	sum /= 2;

	std::size_t m = odds.size(), M = 1 << m;
	Matrix dist(m, std::vector<Weight>(m));
	for (std::size_t i = 0; i < m; ++i) {
		auto dist_v = Dijkstra(graph, odds[i]);
		for (std::size_t j = 0; j < m; ++j) {
			dist[i][j] = dist_v[odds[j]];
		}
	}

	std::vector<Weight> dp(M, INF);
	dp[0] = 0;
	for (std::size_t s = 0; s < M; ++s) {
		for (std::size_t i = 0; i < m; ++i) {
			if (!(s & (1 << i))) {
				for (std::size_t j = i + 1; j < m; ++j) {
					if (!(s & (1 << j))) {
						std::size_t t = s | (1 << i) | (1 << j);
						dp[t] = std::min(dp[t], dp[s] + dist[i][j]);
					}
				}
			}
		}
	}
	return sum + dp[M - 1];
}
#line 4 "test/ChinesePostman.test.cpp"
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int n, m;
	cin >> n >> m;
	Graph g(n);
	for (int i = 0; i < m; ++i) {
		int s, t;
		Weight d;
		cin >> s >> t >> d;
		g[s].emplace_back(t, d);
		g[t].emplace_back(s, d);
	}
	cout << ChinesePostman(g) << '\n';
}
Back to top page