#943675 (C++23) No.2604 Initial Motion

提出ソース

結果

問題	No.2604 Initial Motion
ユーザー	Aeren
提出日時	2024-01-12 22:58:18
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	499 ms / 3,000 ms
コード長	5,095 bytes
コンパイル時間	3,191 ms
コンパイル使用メモリ	262,100 KB
実行使用メモリ	6,676 KB
最終ジャッジ日時	2024-01-12 22:58:31
合計ジャッジ時間	12,797 ms
ジャッジサーバーID （参考情報）	judge15 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	14 ms 6,676 KB
testcase_04	AC	15 ms 6,676 KB
testcase_05	AC	14 ms 6,676 KB
testcase_06	AC	13 ms 6,676 KB
testcase_07	AC	14 ms 6,676 KB
testcase_08	AC	13 ms 6,676 KB
testcase_09	AC	13 ms 6,676 KB
testcase_10	AC	14 ms 6,676 KB
testcase_11	AC	15 ms 6,676 KB
testcase_12	AC	14 ms 6,676 KB
testcase_13	AC	461 ms 6,676 KB
testcase_14	AC	319 ms 6,676 KB
testcase_15	AC	172 ms 6,676 KB
testcase_16	AC	408 ms 6,676 KB
testcase_17	AC	494 ms 6,676 KB
testcase_18	AC	482 ms 6,676 KB
testcase_19	AC	499 ms 6,676 KB
testcase_20	AC	381 ms 6,676 KB
testcase_21	AC	331 ms 6,676 KB
testcase_22	AC	496 ms 6,676 KB
testcase_23	AC	332 ms 6,676 KB
testcase_24	AC	423 ms 6,676 KB
testcase_25	AC	379 ms 6,676 KB
testcase_26	AC	367 ms 6,676 KB
testcase_27	AC	269 ms 6,676 KB
testcase_28	AC	345 ms 6,676 KB
testcase_29	AC	444 ms 6,676 KB
testcase_30	AC	289 ms 6,676 KB
testcase_31	AC	356 ms 6,676 KB
testcase_32	AC	285 ms 6,676 KB
testcase_33	AC	139 ms 6,676 KB
testcase_34	AC	82 ms 6,676 KB
testcase_35	AC	87 ms 6,676 KB
testcase_36	AC	84 ms 6,676 KB
testcase_37	AC	32 ms 6,676 KB
testcase_38	AC	2 ms 6,676 KB
testcase_39	AC	2 ms 6,676 KB
testcase_40	AC	109 ms 6,676 KB
testcase_41	AC	112 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif

template<class T, class C>
struct weighted_flow_network{
	struct E{
		int from, to;
		T capacity, flow;
		C cost;
	};
	vector<vector<int>> adj;
	vector<E> edge;
	int n;
	C cost = 0;
	weighted_flow_network(int n): n(n), adj(n){ }
	void clear_flow(){
		for(auto &e: edge) e.flow = 0;
		cost = 0;
	}
	int insert(int from, int to, T forward_cap, T backward_cap, C cost){
		assert(0 <= from && from < n && 0 <= to && to < n);
		int ind = (int)edge.size();
		adj[from].push_back((int)edge.size());
		edge.push_back({from, to, forward_cap, 0, cost});
		adj[to].push_back((int)edge.size());
		edge.push_back({to, from, backward_cap, 0, -cost});
		return ind;
	}
	void add_flow(int i, T f){
		edge[i].flow += f;
		cost += f * edge[i].cost;
		edge[i ^ 1].flow -= f;
	}
	friend ostream &operator<<(ostream &out, const weighted_flow_network &F){
		out << "\n";
		for(auto &e: F.edge){
			out << "{" << e.from << " -> " << e.to << ", " << e.cost << ", " << e.flow << "/" << e.capacity << "}\n";
		}
		return out;
	}
};

// Requires weighted_flow_network
template<class T, class C>
struct minimum_cost_maximum_flow_spfa{
	static constexpr T eps = (T) 1e-9;
	weighted_flow_network<T, C> &F;
	minimum_cost_maximum_flow_spfa(weighted_flow_network<T, C> &F): F(F), d(F.n), in_queue(F.n), pe(F.n), state(F.n){ }
	// type 0: augment as long as a path exists
	// type 1: augment as long as a negative cost path exists
	vector<C> d;
	vector<int> in_queue, q, pe;
	T expath(int source, int sink, bool type = false){
		fill(d.begin(), d.end(), numeric_limits<C>::max());
		q = {source};
		d[source] = 0;
		in_queue[source] = true;
		int beg = 0;
		bool found = false;
		while(beg < (int)q.size()){
			int u = q[beg ++];
			if(u == sink) found = true;
			in_queue[u] = false;
			for(auto id: F.adj[u]){
				auto &e = F.edge[id];
				if(e.capacity - e.flow > eps && d[u] + e.cost < d[e.to]){
					d[e.to] = d[u] + e.cost;
					pe[e.to] = id;
					if(!in_queue[e.to]){
						q.push_back(e.to);
						in_queue[e.to] = true;
					}
				}
			}
		}
		if(found){
			T push = numeric_limits<T>::max();
			int u = sink;
			while(u != source){
				auto &e = F.edge[pe[u]];
				push = min(push, e.capacity - e.flow);
				u = e.from;
			}
			u = sink;
			assert(push >= 0);
			if(type && d[sink] >= 0) return false;
			while(u != source){
				F.add_flow(pe[u], push);
				u = F.edge[pe[u]].from;
			}
			return push;
		}
		return 0;
	}
	vector<int> stack, state;
	bool try_cycle_cancelling(){
		fill(d.begin(), d.end(), 0);
		q.resize(F.n);
		iota(q.begin(), q.end(), 0);
		fill(in_queue.begin(), in_queue.end(), false);
		fill(pe.begin(), pe.end(), -1);
		int beg = 0, iter = 0;
		auto detect_cycle = [&]()->bool{
			stack.clear();
			fill(state.begin(), state.end(), 0);
			for(auto s = 0; s < F.n; ++ s){
				if(state[s]) continue;
				for(auto u = s; ; ){
					if(state[u]){
						if(state[u] == 1){
							stack.erase(stack.begin(), find(stack.begin(), stack.end(), u));
							assert(!stack.empty() && stack[0] == u);
							T flow = numeric_limits<T>::max();
							for(auto u: stack){
								auto &e = F.edge[pe[u]];
								flow = min(flow, e.capacity - e.flow);
							}
							for(auto u: stack) F.add_flow(pe[u], flow);
							return true;
						}
						break;
					}
					stack.push_back(u);
					state[u] = 1;
					if(!~pe[u]) break;
					u = F.edge[pe[u]].from;
				}
				for(auto u: stack) state[u] = 2;
				stack.clear();
			}
			return false;
		};
		while(beg < (int)q.size()){
			int u = q[beg ++];
			in_queue[u] = false;
			for(auto id: F.adj[u]){
				auto &e = F.edge[id];
				if(e.capacity - e.flow > eps && d[u] + e.cost < d[e.to]){
					d[e.to] = d[u] + e.cost;
					pe[e.to] = id;
					if(++ iter == F.n){
						iter = 0;
						if(detect_cycle()) return true;
					}
					if(!in_queue[e.to]){
						q.push_back(e.to);
						in_queue[e.to] = true;
					}
				}
			}
		}
		return detect_cycle();
	}
	// type 0: min cost max flow
	// type 1: min cost flow
	// O(Augmenting_Paths * SPFA), additional O(SPFA * Cycle_cnt) if negative cycle exists
	pair<T, C> solve(int source, int sink, bool type = false, bool negative_cycle_presence = false){
		F.clear_flow();
		if(negative_cycle_presence) while(try_cycle_cancelling());
		T flow = 0;
		for(T delta; delta = expath(source, sink, type); flow += delta);
		return {flow, F.cost};
	}
};

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int np, n, m;
	cin >> np >> n >> m;
	weighted_flow_network<int, long long> F(n + 2);
	int source = n, sink = n + 1;
	for(auto i = 0; i < np; ++ i){
		int p;
		cin >> p, -- p;
		F.insert(source, p, 1, 0, 0);
	}
	for(auto u = 0; u < n; ++ u){
		int cap;
		cin >> cap;
		F.insert(u, sink, cap, 0, 0);
	}
	for(auto i = 0; i < m; ++ i){
		int u, v;
		long long d;
		cin >> u >> v >> d, -- u, -- v;
		F.insert(u, v, np, 0, d);
		F.insert(v, u, np, 0, d);
	}
	cout << minimum_cost_maximum_flow_spfa(F).solve(source, sink).second << "\n";
	return 0;
}

/*

*/

yukicoder

結果

テストケース

ソースコード