結果
| 問題 |
No.2286 Join Hands
|
| コンテスト | |
| ユーザー |
 emthrm
|
| 提出日時 | 2023-04-29 01:12:11 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 6,286 bytes |
| コンパイル時間 | 3,602 ms |
| コンパイル使用メモリ | 263,948 KB |
| 実行使用メモリ | 1,348,608 KB |
| 最終ジャッジ日時 | 2024-11-17 23:49:25 |
| 合計ジャッジ時間 | 88,288 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 TLE * 26 MLE * 9 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 998244353;
// constexpr int MOD = 1000000007;
constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};
constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};
constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U>
inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
IOSetup() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
std::cout << fixed << setprecision(20);
}
} iosetup;
template <typename T, typename U>
struct MinimumCostSTFlow {
struct Edge {
int dst, rev;
T cap;
U cost;
explicit Edge(const int dst, const T cap, const U cost, const int rev)
: dst(dst), rev(rev), cap(cap), cost(cost) {}
};
const U uinf;
std::vector<std::vector<Edge>> graph;
explicit MinimumCostSTFlow(const int n,
const U uinf = std::numeric_limits<U>::max())
: uinf(uinf), graph(n), tinf(std::numeric_limits<T>::max()), n(n),
has_negative_edge(false), prev_v(n, -1), prev_e(n, -1), dist(n),
potential(n, 0) {}
void add_edge(const int src, const int dst, const T cap, const U cost) {
has_negative_edge |= cost < 0;
graph[src].emplace_back(dst, cap, cost, graph[dst].size());
graph[dst].emplace_back(src, 0, -cost, graph[src].size() - 1);
}
U solve(const int s, const int t, T flow) {
if (flow == 0) [[unlikely]] return 0;
U res = 0;
has_negative_edge ? bellman_ford(s) : dijkstra(s);
while (true) {
if (dist[t] == uinf) return uinf;
res += calc(s, t, &flow);
if (flow == 0) break;
dijkstra(s);
}
return res;
}
U solve(const int s, const int t) {
U res = 0;
T flow = tinf;
bellman_ford(s);
while (potential[t] < 0 && dist[t] != uinf) {
res += calc(s, t, &flow);
dijkstra(s);
}
return res;
}
std::pair<T, U> minimum_cost_maximum_flow(const int s, const int t,
const T flow) {
if (flow == 0) [[unlikely]] return {0, 0};
T f = flow;
U cost = 0;
has_negative_edge ? bellman_ford(s) : dijkstra(s);
while (dist[t] != uinf) {
cost += calc(s, t, &f);
if (f == 0) break;
dijkstra(s);
}
return {flow - f, cost};
}
private:
const T tinf;
const int n;
bool has_negative_edge;
std::vector<int> prev_v, prev_e;
std::vector<U> dist, potential;
std::priority_queue<std::pair<U, int>, std::vector<std::pair<U, int>>,
std::greater<std::pair<U, int>>> que;
void bellman_ford(const int s) {
std::fill(dist.begin(), dist.end(), uinf);
dist[s] = 0;
bool is_updated = true;
for (int step = 0; step < n && is_updated; ++step) {
is_updated = false;
for (int i = 0; i < n; ++i) {
if (dist[i] == uinf) continue;
for (int j = 0; std::cmp_less(j, graph[i].size()); ++j) {
const Edge& e = graph[i][j];
if (e.cap > 0 && dist[e.dst] > dist[i] + e.cost) {
dist[e.dst] = dist[i] + e.cost;
prev_v[e.dst] = i;
prev_e[e.dst] = j;
is_updated = true;
}
}
}
}
assert(!is_updated);
for (int i = 0; i < n; ++i) {
if (dist[i] != uinf) potential[i] += dist[i];
}
}
void dijkstra(const int s) {
std::fill(dist.begin(), dist.end(), uinf);
dist[s] = 0;
que.emplace(0, s);
while (!que.empty()) {
const auto [d, ver] = que.top();
que.pop();
if (dist[ver] < d) continue;
for (int i = 0; std::cmp_less(i, graph[ver].size()); ++i) {
const Edge& e = graph[ver][i];
const U nxt = dist[ver] + e.cost + potential[ver] - potential[e.dst];
if (e.cap > 0 && dist[e.dst] > nxt) {
dist[e.dst] = nxt;
prev_v[e.dst] = ver;
prev_e[e.dst] = i;
que.emplace(dist[e.dst], e.dst);
}
}
}
for (int i = 0; i < n; ++i) {
if (dist[i] != uinf) potential[i] += dist[i];
}
}
U calc(const int s, const int t, T* flow) {
T f = *flow;
for (int v = t; v != s; v = prev_v[v]) {
f = std::min(f, graph[prev_v[v]][prev_e[v]].cap);
}
*flow -= f;
for (int v = t; v != s; v = prev_v[v]) {
Edge& e = graph[prev_v[v]][prev_e[v]];
e.cap -= f;
graph[v][e.rev].cap += f;
}
return potential[t] * f;
}
};
template <typename T>
struct WeightedBipartiteMatching {
explicit WeightedBipartiteMatching(const int left, const int right)
: is_built(false), left(left), right(right), mcf(left + right + 2) {}
void add_edge(const int src, const int dst, const T cost) {
mcf.add_edge(src, left + dst, 1, -cost);
}
T solve() {
assert(!is_built);
is_built = true;
const int s = left + right, t = left + right + 1;
for (int i = 0; i < left; ++i) {
mcf.add_edge(s, i, 1, 0);
}
for (int i = 0; i < right; ++i) {
mcf.add_edge(left + i, t, 1, 0);
}
return -mcf.minimum_cost_maximum_flow(s, t, left).second;
}
std::vector<int> matching() const {
assert(is_built);
std::vector<int> res(left, -1);
for (int i = 0; i < left; ++i) {
for (const auto& e : mcf.graph[i]) {
if (e.cap == 0 && left <= e.dst && e.dst < left + right) {
res[i] = e.dst - left;
break;
}
}
}
return res;
}
private:
bool is_built;
const int left, right;
MinimumCostSTFlow<int, T> mcf;
};
int main() {
int n, m; cin >> n >> m;
vector is_good(n, vector(n, 0));
while (m--) {
int u, v; cin >> u >> v; --u; --v;
is_good[u][v] = true;
}
WeightedBipartiteMatching<int> wbm(n, n);
REP(i, n) FOR(j, i + 1, n) {
wbm.add_edge(i, j, is_good[i][j] ? 2 : 0);
wbm.add_edge(j, i, is_good[i][j] ? 2 : 0);
}
const int ans = wbm.solve() - n;
cout << (ans == n - 1 ? n - 2 : ans) << '\n';
return 0;
}