Submission #3664624

---

Source Code Expand

#include <stdexcept>
#include <cmath>
#include <limits>
#include <type_traits>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <cstddef>
namespace loquat {
using vertex_t = size_t;
}
namespace loquat {
namespace edge_param {
struct to_ {
	vertex_t to;
	explicit to_(vertex_t t = 0)
		: to(t)
	{ }
};
template <typename T>
struct weight_ {
	using weight_type = T;
	weight_type weight;
	weight_(const weight_<T>& w)
		: weight(w.weight)
	{ }
	explicit weight_(const weight_type& w = weight_type())
		: weight(w)
	{ }
};
template <typename T>
using weight = weight_<T>;
template <typename T>
struct capacity_ {
	using capacity_type = T;
	capacity_type capacity;
	explicit capacity_(const capacity_type& c = capacity_type())
		: capacity(c)
	{ }
};
template <typename T>
using capacity = capacity_<T>;
}
namespace detail {
template <typename T, typename... Params>
struct edge_param_wrapper : public T, edge_param_wrapper<Params...> {
	using self_type = edge_param_wrapper<T, Params...>;
	using next_type = edge_param_wrapper<Params...>;
	edge_param_wrapper(const self_type& e)
		: T(static_cast<const T&>(e))
		, next_type(static_cast<const next_type&>(e))
	{ }
	template <typename U, typename... Args>
	explicit edge_param_wrapper(U&& x, Args&&... args)
		: T(std::forward<U>(x))
		, edge_param_wrapper<Params...>(std::forward<Args>(args)...)
	{ }
};
template <typename T>
struct edge_param_wrapper<T> : public T {
	using self_type = edge_param_wrapper<T>;
	edge_param_wrapper(const self_type& e)
		: T(e)
	{ }
	template <typename U>
	explicit edge_param_wrapper(U&& x)
		: T(std::forward<U>(x))
	{ }
};
}
template <typename... Params>
struct edge : public detail::edge_param_wrapper<edge_param::to_, Params...> {
	using self_type = edge<Params...>;
	using wrapper_type = detail::edge_param_wrapper<edge_param::to_, Params...>;
	edge(const self_type& e)
		: wrapper_type(static_cast<const wrapper_type&>(e))
	{ }
	template <typename... Args>
	explicit edge(vertex_t to, Args&&... rest)
		: wrapper_type(to, std::forward<Args>(rest)...)
	{ }
};
}
namespace loquat {
template <typename EdgeType>
struct has_weight {
private:
	template <typename U>
	static std::true_type check_type(typename U::weight_type *);
	template <typename U>
	static auto check_member(const U& x)
		-> decltype(x.weight, std::true_type());
public:
	static const bool value =
		decltype(check_type<EdgeType>(nullptr))::value &&
		decltype(check_member(std::declval<EdgeType>()))::value;
};
}
namespace loquat {
template <typename EdgeType>
class adjacency_list {
public:
	using edge_type = EdgeType;
	using edge_list = std::vector<edge_type>;
private:
	std::vector<std::vector<EdgeType>> m_edges;
public:
	explicit adjacency_list(size_t n)
		: m_edges(n)
	{ }
	size_t size() const {
		return m_edges.size();
	}
	const edge_list& operator[](vertex_t u) const {
		return m_edges[u];
	}
	edge_list& operator[](vertex_t u){
		return m_edges[u];
	}
	template <typename... Args>
	void add_edge(vertex_t from, Args&&... args){
		m_edges[from].emplace_back(std::forward<Args>(args)...);
	}
	void add_edge(vertex_t from, const edge_type& e){
		m_edges[from].emplace_back(e);
	}
};
}
namespace loquat {
namespace detail {
template <typename EdgeType>
auto negate_weight(EdgeType& e)
	-> typename std::enable_if<has_weight<EdgeType>::value, void>::type
{
	e.weight = -e.weight;
}
}
template <typename EdgeType>
struct residual_edge : public EdgeType {
	using base_type = EdgeType;
	size_t rev;
	residual_edge(const base_type& e, size_t rev)
		: base_type(e)
		, rev(rev)
	{ }
};
template <typename EdgeType>
adjacency_list<residual_edge<EdgeType>>
make_residual(const adjacency_list<EdgeType>& graph){
	using edge_type = EdgeType;
	using residual_type = residual_edge<edge_type>;
	using capacity_type = typename edge_type::capacity_type;
	const size_t n = graph.size();
	adjacency_list<residual_type> result(n);
	for(vertex_t u = 0; u < n; ++u){
		for(const auto& e : graph[u]){
			result.add_edge(u, residual_type(e, 0));
		}
	}
	for(vertex_t u = 0; u < n; ++u){
		const size_t m = graph[u].size();
		for(size_t i = 0; i < m; ++i){
			auto e = graph[u][i];
			const auto v = e.to;
			e.to = u;
			e.capacity = capacity_type();
			detail::negate_weight(e);
			result[u][i].rev = result[v].size();
			result.add_edge(v, residual_type(e, i));
		}
	}
	return result;
}
}
namespace loquat {
template <typename EdgeType, typename Predicate>
adjacency_list<EdgeType> filter(
	const adjacency_list<EdgeType>& graph,
	Predicate pred)
{
	const size_t n = graph.size();
	adjacency_list<EdgeType> result(n);
	for(vertex_t u = 0; u < n; ++u){
		for(const auto& e : graph[u]){
			if(pred(u, e)){ result.add_edge(u, e); }
		}
	}
	return result;
}
}
namespace loquat {
template <typename T>
constexpr inline auto positive_infinity() noexcept
	-> typename std::enable_if<std::is_integral<T>::value, T>::type
{
	return std::numeric_limits<T>::max();
}
template <typename T>
constexpr inline auto is_positive_infinity(T x) noexcept
	-> typename std::enable_if<std::is_integral<T>::value, bool>::type
{
	return x == std::numeric_limits<T>::max();
}
}
namespace loquat {
class no_solution_error : public std::runtime_error {
public:
	explicit no_solution_error(const char *what)
		: std::runtime_error(what)
	{ }
};
}
namespace loquat {
template <typename EdgeType>
std::vector<typename EdgeType::weight_type>
sssp_bellman_ford(vertex_t source, const adjacency_list<EdgeType>& graph){
	using weight_type = typename EdgeType::weight_type;
	const auto inf = positive_infinity<weight_type>();
	const auto n = graph.size();
	std::vector<weight_type> result(n, inf);
	result[source] = weight_type();
	bool finished = false;
	for(size_t iter = 0; !finished && iter < n; ++iter){
		finished = true;
		for(loquat::vertex_t u = 0; u < n; ++u){
			if(loquat::is_positive_infinity(result[u])){ continue; }
			for(const auto& e : graph[u]){
				const auto v = e.to;
				if((result[u] + e.weight) < result[v]){
					result[v] = result[u] + e.weight;
					finished = false;
				}
			}
		}
	}
	if(!finished){
		throw no_solution_error("graph has a negative cycle");
	}
	return result;
}
}
namespace loquat {
template <typename EdgeType>
typename EdgeType::weight_type
mincostflow_primal_dual(
	typename EdgeType::capacity_type flow,
	vertex_t source,
	vertex_t sink,
	adjacency_list<EdgeType>& graph)
{
	using edge_type = EdgeType;
	using weight_type = typename edge_type::weight_type;
	const auto inf = positive_infinity<weight_type>();
	const auto n = graph.size();
	const auto predicate =
		[](vertex_t, const edge_type& e) -> bool { return e.capacity > 0; };
	auto h = sssp_bellman_ford(source, filter(graph, predicate));
	std::vector<vertex_t> prev_vertex(n);
	std::vector<size_t> prev_edge(n);
	weight_type result = 0;
	while(flow > 0){
		using pair_type = std::pair<weight_type, vertex_t>;
		std::priority_queue<
			pair_type, std::vector<pair_type>, std::greater<pair_type>> pq;
		std::vector<weight_type> d(n, inf);
		pq.emplace(0, source);
		d[source] = weight_type();
		while(!pq.empty()){
			const auto p = pq.top();
			pq.pop();
			const auto u = p.second;
			if(d[u] < p.first){ continue; }
			for(size_t i = 0; i < graph[u].size(); ++i){
				const auto& e = graph[u][i];
				if(e.capacity <= 0){ continue; }
				const auto v = e.to;
				const auto t = d[u] + e.weight + h[u] - h[v];
				if(d[v] <= t){ continue; }
				d[v] = t;
				prev_vertex[v] = u;
				prev_edge[v] = i;
				pq.emplace(t, v);
			}
		}
		if(is_positive_infinity(d[sink])){
			throw no_solution_error("there are no enough capacities to flow");
		}
		for(size_t i = 0; i < n; ++i){ h[i] += d[i]; }
		weight_type f = flow;
		for(vertex_t v = sink; v != source; v = prev_vertex[v]){
			const auto u = prev_vertex[v];
			f = std::min(f, graph[u][prev_edge[v]].capacity);
		}
		flow -= f;
		result += f * h[sink];
		for(vertex_t v = sink; v != source; v = prev_vertex[v]){
			const auto u = prev_vertex[v];
			auto& e = graph[u][prev_edge[v]];
			e.capacity -= f;
			graph[v][e.rev].capacity += f;
		}
	}
	return result;
}
}
using namespace std;
using edge = loquat::edge<
	loquat::edge_param::weight<int>,
	loquat::edge_param::capacity<int>>;
int main(){
	ios_base::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	vector<int> a(n), b(n);
	for(int i = 0; i < n; ++i){ cin >> a[i]; --a[i]; }
	for(int i = 0; i < n; ++i){ cin >> b[i]; --b[i]; }
	vector<vector<int>> conn(n);
	vector<int> usage(n);
	int score = 0;
	for(int i = 0; i < n; ++i){
		const int u = max(a[i], b[i]);
		const int v = min(a[i], b[i]);
		conn[u].push_back(v);
		++usage[u];
		score += u + 1;
	}
	int variations = 0;
	for(int i = 0; i < n; ++i){
		if(usage[i] >= 1){ ++variations; }
	}
	if(variations >= k){
		cout << score << endl;
		return 0;
	}
	loquat::adjacency_list<edge> g(2 * n + 2);
	const int source = 2 * n, sink = source + 1;
	for(int r = 0; r < n; ++r){
		if(usage[r] == 1){
			continue;
		}else if(usage[r] == 0){
			g.add_edge(r + n, sink, 0, 1);
			continue;
		}else{
			vector<bool> vis(n);
			vis[r] = true;
			for(int u = n - 1; u >= 0; --u){
				if(!vis[u]){ continue; }
				for(const int v : conn[u]){ vis[v] = true; }
			}
			for(int i = 0; i < r; ++i){
				if(!vis[i]){ continue; }
				g.add_edge(r, i + n, r - i, 1);
			}
			g.add_edge(source, r, 0, usage[r] - 1);
		}
	}
	auto residual = loquat::make_residual(g);
	score -= loquat::mincostflow_primal_dual(k - variations, source, sink, residual);
	cout << score << endl;
	return 0;
}

Submission Info

Judge Result