結果
| 問題 |
No.2286 Join Hands
|
| コンテスト | |
| ユーザー |
 hos.lyric
|
| 提出日時 | 2023-04-28 22:59:57 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,194 bytes |
| コンパイル時間 | 1,262 ms |
| コンパイル使用メモリ | 118,540 KB |
| 実行使用メモリ | 15,808 KB |
| 最終ジャッジ日時 | 2024-11-17 21:57:24 |
| 合計ジャッジ時間 | 91,274 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 TLE * 28 |
ソースコード
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
// Minimum cost flow by successive shortest paths.
// Assumes that there exists no negative-cost cycle.
// TODO: Check the range of intermediate values.
template <class Flow, class Cost> struct MinCostFlow {
// Watch out when using types other than int and long long.
static constexpr Flow FLOW_EPS = 1e-10L;
static constexpr Flow FLOW_INF = std::numeric_limits<Flow>::max();
static constexpr Cost COST_EPS = 1e-10L;
static constexpr Cost COST_INF = std::numeric_limits<Cost>::max();
int n, m;
vector<int> ptr, nxt, zu;
vector<Flow> capa;
vector<Cost> cost;
explicit MinCostFlow(int n_) : n(n_), m(0), ptr(n_, -1) {}
void ae(int u, int v, Flow w, Cost c) {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
assert(0 <= w);
nxt.push_back(ptr[u]); zu.push_back(v); capa.push_back(w); cost.push_back( c); ptr[u] = m++;
nxt.push_back(ptr[v]); zu.push_back(u); capa.push_back(0); cost.push_back(-c); ptr[v] = m++;
}
vector<Cost> pot, dist;
vector<bool> vis;
vector<int> pari;
// cost slopes[j] per flow when flows[j] <= flow <= flows[j + 1]
vector<Flow> flows;
vector<Cost> slopes;
// Finds a shortest path from s to t in the residual graph.
// O((n + m) log m) time.
// Assumes that the members above are set.
// The distance to a vertex might not be determined if it is >= dist[t].
// You can pass t = -1 to find a shortest path to each vertex.
void shortest(int s, int t) {
using Entry = pair<Cost, int>;
priority_queue<Entry, vector<Entry>, std::greater<Entry>> que;
for (int u = 0; u < n; ++u) { dist[u] = COST_INF; vis[u] = false; }
for (que.emplace(dist[s] = 0, s); !que.empty(); ) {
const Cost c = que.top().first;
const int u = que.top().second;
que.pop();
if (vis[u]) continue;
vis[u] = true;
if (u == t) return;
for (int i = ptr[u]; ~i; i = nxt[i]) if (capa[i] > FLOW_EPS) {
const int v = zu[i];
if (!vis[v]) {
const Cost cc = c + cost[i] + pot[u] - pot[v];
if (dist[v] > cc) { que.emplace(dist[v] = cc, v); pari[v] = i; }
}
}
}
}
// Finds a minimum cost flow from s to t of amount min{(max flow), limFlow}.
// Bellman-Ford takes O(n m) time, or O(m) time if there is no negative-cost
// edge, or cannot stop if there exists a negative-cost cycle.
// min{(max flow), limFlow} shortest paths if Flow is an integral type.
pair<Flow, Cost> run(int s, int t, Flow limFlow = FLOW_INF) {
assert(0 <= s); assert(s < n);
assert(0 <= t); assert(t < n);
assert(s != t);
assert(0 <= limFlow);
pot.assign(n, 0);
for (; ; ) {
bool upd = false;
for (int i = 0; i < m; ++i) if (capa[i] > FLOW_EPS) {
const int u = zu[i ^ 1], v = zu[i];
const Cost cc = pot[u] + cost[i];
if (pot[v] > cc + COST_EPS) { pot[v] = cc; upd = true; }
}
if (!upd) break;
}
dist.resize(n);
vis.resize(n);
pari.resize(n);
Flow flow = 0;
Cost cost = 0;
flows.clear(); flows.push_back(0);
slopes.clear();
for (; flow < limFlow; ) {
shortest(s, t);
if (!vis[t]) break;
for (int u = 0; u < n; ++u) pot[u] += min(dist[u], dist[t]);
Flow f = limFlow - flow;
for (int v = t; v != s; ) {
const int i = pari[v]; if (f > capa[i]) { f = capa[i]; } v = zu[i ^ 1];
}
for (int v = t; v != s; ) {
const int i = pari[v]; capa[i] -= f; capa[i ^ 1] += f; v = zu[i ^ 1];
}
flow += f;
cost += f * (pot[t] - pot[s]);
flows.push_back(flow);
slopes.push_back(pot[t] - pot[s]);
}
return make_pair(flow, cost);
}
};
////////////////////////////////////////////////////////////////////////////////
int N, M;
vector<int> A, B;
int main() {
for (; ~scanf("%d%d", &N, &M); ) {
A.resize(M);
B.resize(M);
for (int i = 0; i < M; ++i) {
scanf("%d%d", &A[i], &B[i]);
--A[i];
--B[i];
}
MinCostFlow<int, int> mcf(2 + N + N + N + N);
auto out = [&](int u) -> int { return 2 + u; };
auto in = [&](int u) -> int { return 2 + N + u; };
auto toL = [&](int u) -> int { return 2 + N + N + u; };
auto toR = [&](int u) -> int { return 2 + N + N + N + u; };
for (int u = 0; u < N; ++u) {
mcf.ae(0, out(u), 1, 0);
mcf.ae(in(u), 1, 1, 0);
mcf.ae(toL(u), in(u), 1, 0);
mcf.ae(toR(u), in(u), 1, 0);
// discard
if (u - 1 >= 0) mcf.ae(out(u), toL(u - 1), 1, 0);
if (u + 1 < N) mcf.ae(out(u), toR(u + 1), 1, 0);
}
for (int u = 0; u < N - 1; ++u) {
mcf.ae(toL(u + 1), toL(u), N, 0);
mcf.ae(toR(u), toR(u + 1), N, 0);
}
// use
for (int i = 0; i < M; ++i) {
mcf.ae(out(A[i]), in(B[i]), 1, -1);
mcf.ae(out(B[i]), in(A[i]), 1, -1);
}
const auto res = mcf.run(0, 1, N);
// cerr<<"res = "<<res<<endl;
assert(res.first == N);
const int ans = -res.second;
printf("%d\n", 2 * ans - N);
}
return 0;
}