結果

問題 No.2464 To DAG
ユーザー AerenAeren
提出日時 2023-09-08 22:18:50
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,279 bytes
コンパイル時間 4,344 ms
コンパイル使用メモリ 376,772 KB
実行使用メモリ 60,500 KB
最終ジャッジ日時 2024-06-26 15:26:36
合計ジャッジ時間 29,411 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 207 ms
37,108 KB
testcase_03 WA -
testcase_04 AC 1,087 ms
42,124 KB
testcase_05 AC 766 ms
40,032 KB
testcase_06 AC 617 ms
38,872 KB
testcase_07 AC 1,135 ms
35,356 KB
testcase_08 AC 945 ms
35,548 KB
testcase_09 AC 606 ms
30,524 KB
testcase_10 AC 489 ms
29,840 KB
testcase_11 AC 353 ms
22,116 KB
testcase_12 AC 261 ms
18,880 KB
testcase_13 WA -
testcase_14 AC 485 ms
40,636 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 115 ms
22,440 KB
testcase_23 AC 119 ms
23,000 KB
testcase_24 AC 108 ms
23,120 KB
testcase_25 AC 114 ms
23,020 KB
testcase_26 AC 93 ms
14,632 KB
testcase_27 AC 909 ms
60,500 KB
testcase_28 AC 966 ms
60,368 KB
testcase_29 AC 838 ms
58,840 KB
testcase_30 AC 618 ms
39,640 KB
testcase_31 AC 767 ms
37,560 KB
testcase_32 AC 876 ms
36,256 KB
testcase_33 WA -
testcase_34 WA -
testcase_35 AC 105 ms
22,920 KB
testcase_36 AC 99 ms
22,980 KB
testcase_37 AC 70 ms
22,864 KB
testcase_38 AC 71 ms
22,900 KB
testcase_39 AC 15 ms
14,976 KB
testcase_40 AC 15 ms
14,848 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <x86intrin.h>
using namespace std;
using namespace numbers;

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

// Requires flow_network
template<class T>
struct dinic_maximum_flow{
	static constexpr T eps = (T)1e-9, inf = numeric_limits<T>::max();
	flow_network<T> &F;
	dinic_maximum_flow(flow_network<T> &F): F(F), ptr(F.n), level(F.n), q(F.n){ }
	vector<int> ptr, level, q;
	bool bfs(int source, int sink){
		fill(level.begin(), level.end(), -1);
		q[0] = sink;
		level[sink] = 0;
		for(auto beg = 0, end = 1; beg < end; ){
			int i = q[beg ++];
			for(auto ind: F.adj[i]){
				auto &e = F.edge[ind];
				auto &re = F.edge[ind ^ 1];
				if(re.capacity - re.flow > eps && level[e.to] == -1){
					level[e.to] = level[i] + 1;
					if(e.to == source) return true;
					q[end ++] = e.to;
				}
			}
		}
		return false;
	}
	T dfs(int u, T w, int sink){
		if(u == sink) return w;
		int &j = ptr[u];
		while(j >= 0){
			int ind = F.adj[u][j];
			auto &e = F.edge[ind];
			if(e.capacity - e.flow > eps && level[e.to] == level[u] - 1){
				T flow = dfs(e.to, min(e.capacity - e.flow, w), sink);
				if(flow > eps){
					F.add_flow(ind, flow);
					return flow;
				}
			}
			-- j;
		}
		return 0;
	}
	// Find a maximum source-sink flow
	// O(V^2 E) ( O(E min(V^2/3, E^1/2)) for unit network )
	T maximum_flow(int source, int sink){
		assert(0 <= source && source < F.n && 0 <= sink && sink < F.n);
		T flow = 0;
		while(bfs(source, sink)){
			for(auto i = 0; i < F.n; ++ i) ptr[i] = (int)F.adj[i].size() - 1;
			T sum = 0;
			while(true){
				T add = dfs(source, inf, sink);
				if(add <= eps) break;
				sum += add;
			}
			if(sum <= eps) break;
			flow += sum;
		}
		return flow;
	}
	// Find a minimum source-sink cut
	// O(V^2 E) ( O(E min(V^2/3, E^1/2)) for unit network )
	tuple<T, vector<int>, vector<int>> minimum_cut(int source, int sink){
		T cut_weight = maximum_flow(source, sink);
		vector<int> left, right;
		for(auto u = 0; u < F.n; ++ u) (!~level[u] ? left : right).push_back(u);
		return {cut_weight, left, right};
	}
};

// Requires flow_network
template<class T>
struct flow_decomposition{
	flow_network<T> &F;
	vector<vector<int>> paths;
	vector<T> path_flows;
	vector<vector<int>> cycles;
	vector<T> cycle_flows;
	flow_decomposition(flow_network<T> &F): F(F){ }
	void decompose(int source, int sink){
		vector<T> fs(F.edge.size());
		for(auto i = 0; i < (int)F.edge.size(); ++ i) fs[i] = F.edge[i].flow;
		paths.clear();
		path_flows.clear();
		cycles.clear();
		cycle_flows.clear();
		int n = F.n;
		static constexpr T eps = (T)1e-9;
		vector<int> ptr(n);
		for(auto i = 0; i < n; ++ i) ptr[i] = (int)F.adj[i].size() - 1;
		vector<int> was(n, -1);
		int start = source;
		for(auto iter = 0; ; ++ iter){
			bool found_start = false;
			while(true){
				if(ptr[start] >= 0){
					int id = F.adj[start][ptr[start]];
					if(fs[id] > eps){
						found_start = true;
						break;
					}
					-- ptr[start];
					continue;
				}
				start = (start + 1) % n;
				if(start == source) break;
			}
			if(!found_start) break;
			vector<int> path;
			bool is_cycle = false;
			int u = start;
			while(true){
				if(u == sink) break;
				if(was[u] == iter){
					bool found = false;
					for(auto i = 0; i < (int)path.size(); ++ i){
						int id = path[i];
						auto &e = F.edge[id];
						if(e.from == u){
							path.erase(path.begin(), path.begin() + i);
							found = true;
							break;
						}
					}
					assert(found);
					is_cycle = true;
					break;
				}
				was[u] = iter;
				bool found = false;
				while(ptr[u] >= 0){
					int id = F.adj[u][ptr[u]];
					if(fs[id] > eps){
						path.push_back(id);
						u = F.edge[id].to;
						found = true;
						break;
					}
					-- ptr[u];
				}
				assert(found);
			}
			T path_flow = numeric_limits<T>::max();
			for(auto id : path) path_flow = min(path_flow, fs[id]);
			for(auto id : path){
				fs[id] -= path_flow;
				fs[id ^ 1] += path_flow;
			}
			if(is_cycle){
				cycles.push_back(path);
				cycle_flows.push_back(path_flow);
			}
			else{
				paths.push_back(path);
				path_flows.push_back(path_flow);
			}
		}
		for(const auto &f: fs) assert(-eps <= f && f <= eps);
	}
};

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n, m;
	cin >> n >> m;
	vector<int> d(n);
	int source = n, sink = n + 1;
	flow_network<int> F(n + 2);
	for(auto i = 0; i < m; ++ i){
		int u, v;
		cin >> u >> v, -- u, -- v;
		F.insert(u, v, 1, 0);
		++ d[u];
		-- d[v];
	}
	for(auto u = 0; u < n; ++ u){
		if(d[u] > 0){
			F.insert(source, u, d[u], 0);
		}
		else if(d[u] < 0){
			F.insert(u, sink, -d[u], 0);
		}
	}
	dinic_maximum_flow<int>(F).maximum_flow(source, sink);
	flow_decomposition<int> FD(F);
	FD.decompose(source, sink);
	vector<array<int, 2>> edge;
	for(auto path: FD.paths){
		for(auto id: path){
			auto &e = F.edge[id];
			if(e.from != source && e.to != sink){
				edge.push_back({e.from, e.to});
			}
		}
	}
	cout << n << " " << (int)edge.size() << "\n";
	for(auto [u, v]: edge){
		cout << u + 1 << " " << v + 1 << "\n";
	}
	return 0;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////
0