結果
| 問題 |
No.2464 To DAG
|
| コンテスト | |
| ユーザー |
 Aeren
|
| 提出日時 | 2023-09-08 22:18:50 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 31 WA * 8 |
ソースコード
#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 //
// //
////////////////////////////////////////////////////////////////////////////////////////