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

提出ソース

結果

問題	No.2604 Initial Motion
ユーザー	Aeren
提出日時	2024-01-13 00:54:59
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	474 ms / 3,000 ms
コード長	5,200 bytes
コンパイル時間	2,956 ms
コンパイル使用メモリ	261,028 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-09-28 00:54:18
合計ジャッジ時間	12,004 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	13 ms 5,376 KB
testcase_04	AC	13 ms 5,376 KB
testcase_05	AC	13 ms 5,376 KB
testcase_06	AC	14 ms 5,376 KB
testcase_07	AC	13 ms 5,376 KB
testcase_08	AC	13 ms 5,376 KB
testcase_09	AC	13 ms 5,376 KB
testcase_10	AC	14 ms 5,376 KB
testcase_11	AC	14 ms 5,376 KB
testcase_12	AC	14 ms 5,376 KB
testcase_13	AC	428 ms 5,376 KB
testcase_14	AC	304 ms 5,376 KB
testcase_15	AC	165 ms 5,376 KB
testcase_16	AC	391 ms 5,376 KB
testcase_17	AC	474 ms 5,376 KB
testcase_18	AC	470 ms 5,376 KB
testcase_19	AC	465 ms 5,376 KB
testcase_20	AC	372 ms 5,376 KB
testcase_21	AC	331 ms 5,376 KB
testcase_22	AC	459 ms 5,376 KB
testcase_23	AC	330 ms 5,376 KB
testcase_24	AC	417 ms 5,376 KB
testcase_25	AC	367 ms 5,376 KB
testcase_26	AC	364 ms 5,376 KB
testcase_27	AC	266 ms 5,376 KB
testcase_28	AC	341 ms 5,376 KB
testcase_29	AC	410 ms 5,376 KB
testcase_30	AC	290 ms 5,376 KB
testcase_31	AC	344 ms 5,376 KB
testcase_32	AC	251 ms 5,376 KB
testcase_33	AC	127 ms 5,376 KB
testcase_34	AC	77 ms 5,376 KB
testcase_35	AC	79 ms 5,376 KB
testcase_36	AC	79 ms 5,376 KB
testcase_37	AC	29 ms 5,376 KB
testcase_38	AC	3 ms 5,376 KB
testcase_39	AC	3 ms 5,376 KB
testcase_40	AC	103 ms 5,376 KB
testcase_41	AC	102 ms 5,376 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 link(int from, int to, T cap, C cost){
		assert(0 <= from && from < n && 0 <= to && to < n);
		int ind = orient(from, to, cap, cost);
		orient(to, from, cap, cost);
		return ind;
	}
	int orient(int from, int to, T 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, cap, 0, cost});
		adj[to].push_back((int)edge.size());
		edge.push_back({to, from, 0, 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.orient(source, p, 1, 0);
	}
	for(auto u = 0; u < n; ++ u){
		int cap;
		cin >> cap;
		F.orient(u, sink, cap, 0);
	}
	for(auto i = 0; i < m; ++ i){
		int u, v;
		long long d;
		cin >> u >> v >> d, -- u, -- v;
		F.link(u, v, np, d);
	}
	cout << minimum_cost_maximum_flow_spfa(F).solve(source, sink).second << "\n";
	return 0;
}

/*

*/

yukicoder

結果

テストケース

ソースコード