Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifdef LOCAL
- //#define _GLIBCXX_DEBUG
- // #pragma comment(linker, "/STACK:102400000,102400000") // 在 Windows 上有效
- #endif
- #pragma GCC optimize("Ofast") // Ofast 等效于 -O3 -ffast-math
- #include <bits/stdc++.h>
- using namespace std;
- #define FAST_READ ios::sync_with_stdio(false); cin.tie(nullptr);
- #ifdef LOCAL
- #define see(x) cout <<"<DBG> " << #x << ": " << (x) << endl
- #endif
- #ifndef LOCAL
- #define see(x)
- #endif
- template<typename T> void dprintln(const T &t) { cout << t << endl; } // for debug use
- template<typename T, typename ...Args> void dprintln(const T &t, const Args &...rest) { cout << t << ' '; dprintln(rest...); }
- template<typename T> void println(const T &t) { cout << t << '\n'; }
- template<typename T, typename ...Args> void println(const T &t, const Args &...rest) { cout << t << ' '; println(rest...); }
- template<typename T> void print(const T &t) { cout << t << ' '; }
- template<typename T, typename ...Args> void print(const T &t, const Args &...rest) { cout << t << ' '; print(rest...); }
- // this overload is chosen when there's only one argument
- template<class T> void scan(T &t) { cin >> t; }
- template<class T, class ...Args> void scan(T &a, Args &...rest) { cin >> a; scan(rest...); }
- template <typename T> void read(vector<T> &vec) {for(auto &x: vec) cin >> x;}
- using ull = unsigned long long;
- using ll = long long;
- using ul = unsigned long;
- using vl = vector<ll>;
- using vi = vector<int>;
- using pii = pair<int,int>;
- using vb = vector<bool>;
- using vpii = vector<pii>;
- template <typename int_t>
- inline int_t lowbit(int_t x) {return x & -x;}
- #define rng(i, a, b) for(int i = (a); i < (b); ++i)
- #define down(i, b, a) for (int i = (b); i >= (a); i--)
- #define rep(n) for(int _ = 0, __ = (int)n; _ < __; _++)
- #define stp(i, a, b, c) for (int i = (a); i < (b); i += (c))
- #define FOR(x, cont) for (const auto &x: cont)
- #define For(x, cont) for (auto &x: cont)
- #define all(x) begin(x), end(x)
- #define pb push_back
- #define mp make_pair
- #define eb emplace_back
- #define SZ(x) (int)(x).size()
- template <typename T, typename Comp = less<T>>
- using pq = priority_queue<T, vector<T>, Comp>;
- #define popcnt(x) __builtin_popcountll((x))
- #define SET(arr, v) memset(arr, (v), sizeof (arr))
- #define UNIQ(vec) (vec).erase(unique(all(vec)), end(vec))
- #define LB(cont, x) int(lower_bound(all(cont), x) - begin(cont))
- #define AI(name, n, m) vv<int> name(n, vi(m));
- #define AL(name, n, m) vv<ll> name(size_t(n), vl(size_t(m)));
- auto bet = [](const ll x, const ll y, const ll i) {
- return x <= i && i <= y;
- };
- template<typename T1, typename T2>
- T1 ceil(T1 x, T2 y) { // y >= 1,是整数。需要注意 x + y - 1 是否会溢出
- return (x + y - 1) / y;
- }
- inline int h_bit(unsigned long long x) {
- return sizeof(unsigned long long) * 8 - 1 - __builtin_clzll(x);
- }
- int pow2(int x){ // power of 2
- return 1 << (h_bit((ull)x) + (x != lowbit(x)));
- }
- template <typename T>
- struct bit {
- vector<T> a;
- function<T(T,T)> bin_op;
- explicit bit(int n, function<T(T,T)> bin_op = [](const T &a, const T &b){return max(a, b);}, int v = 0):bin_op(bin_op){
- a.resize((ul)n + 1);
- for (int i = 1; i <= n; ++i) a[i] = v;
- }
- T prefix(T x) {
- T res = 0;
- while (x) {
- res = bin_op(res, a[x]);
- // res += a[x];
- x -= x & -x;
- }
- return res;
- }
- T sum(int l, int r) {
- if (l > r) return 0;
- return sum(r) - sum(l - 1);
- }
- void modify(int x, T v) {
- while (x < a.size()) {
- a[x] = bin_op(a[x], v);
- x += x & -x;
- }
- }
- void clear(){
- fill(a.begin(), a.end(), 0);
- }
- };
- template <typename T>
- struct r_bit {
- vector<T> a;
- function<T(T,T)> bin_op;
- explicit r_bit(int n, function<T(T,T)> bin_op = [](const T &a, const T &b){return max(a, b);}, int v = 0):bin_op(bin_op){
- a.resize((ul)n + 1);
- for (int i = 1; i <= n; ++i) a[i] = v;
- }
- T suffix(T x) {
- T res = 0;
- while (x < a.size()) {
- res = bin_op(res, a[x]);
- // res += a[x];
- x += x & -x;
- }
- return res;
- }
- T sum(int l, int r) {
- if (l > r) return 0;
- return sum(r) - sum(l - 1);
- }
- void modify(int x, T v) {
- while (x > 0) {
- a[x] = bin_op(a[x], v);
- x -= x & -x;
- }
- }
- void clear(){
- fill(a.begin(), a.end(), 0);
- }
- };
- vi get_prime(int n) {
- vi minp((ul)n + 1), p;
- for (int i = 2; i <= n; i++) {
- if (!minp[i]) {
- minp[i] = i;
- p.pb(i);
- }
- FOR(x, p) {
- if (x <= minp[i] && x * i <= n)
- minp[x * i] = x;
- else break;
- }
- }
- return p;
- }
- const int mod = 998244353; //记住 mod 的行号!
- inline void mul(int &x, const int y) {
- x = int(ll(x) * y % mod);
- }
- inline int Mul(int x, const int y) {
- return (int)(ll(x) * y % mod);
- }
- inline void add(int &x, const int y) {
- x += y;
- if (x >= mod) x -= mod;
- }
- inline int Add(int x, int y) {
- x += y;
- if (x >= mod) x -= mod;
- return x;
- }
- inline int Sub(int x, int y) {
- x -= y; if (x < 0) x += mod;
- return x;
- }
- inline ll submod(ll x, ll y) {
- return x >= y ? x - y : x - y + mod;
- }
- inline ll addmod(ll x, ll y) {
- x += y;
- return x >= mod ? x - mod : x;
- }
- inline void sub_mod(ll &x, const ll y) {
- x -= y;
- if (x < 0) x += mod;
- }
- // alias templates
- template<typename T> using vv = vector<vector<T>>;
- template <typename T1, typename T2 = T1> using vp = vector<pair<T1,T2>>;
- template<typename T, int n> using va = vector<array<T,n>>;
- #ifdef __GNUC__
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- template <typename T>
- using rank_tree = __gnu_pbds::tree<
- T,
- __gnu_pbds::null_type,
- less<T>,
- __gnu_pbds::rb_tree_tag,
- __gnu_pbds::tree_order_statistics_node_update>;
- #endif
- //union-find 并查集
- struct UF{
- vi par, sz;
- int tot;
- explicit UF(int n) { //0-indexed
- par.assign(n, 0);
- sz.assign(n, 1);
- rng (i, 0, n) par[i] = i;
- tot = n;
- }
- int find(int x) {
- return x == par[x] ? x : par[x] = find(par[x]);
- }
- bool unite(int x, int y) {
- int rx = find(x), ry = find(y);
- if(rx != ry) {
- par[rx] = ry;
- --tot;
- return true;
- }
- return false;
- }
- };
- int fp (int x, ll n) { //fast power: hat off to quailty
- if(n < 0) {
- x = fp(x, mod - 2);
- n = -n;
- }
- int ans = 1;
- while(n){
- if(n&1) mul(ans, x);
- n /= 2;
- mul(x, x);
- }
- return ans;
- }
- vi get_popcnt(int n) {
- vi res((ul)n + 1);
- rng (i, 0, n) {
- if (i * 2 <= n) res[i * 2] = res[i];
- if ((i & 1) == 0) res[i + 1] = res[i] + 1;
- }
- return res;
- }
- using idx_t = long;
- template <typename T, typename Compare = std::less<T>>
- struct ST{
- size_t n; // 0-indexed
- vv<T> a;
- template <typename ptr_t>
- ST(ptr_t beg, ptr_t end):n(end-beg){
- a.resize((size_t)h_bit(n)+1); // 注意:不能写成 h_bit(n)
- a[0].assign(beg, end);
- rng (i, 0, SZ(a)-1) {
- a[i+1].resize(n);
- rng(j, 0, n - (1 << i)) {
- a[i+1][j] = min(a[i][j], a[i][j+(1<<i)], Compare());
- }
- rng(j, n-(1 << i), n) {
- a[i+1][j] = a[i][j];
- }
- }
- }
- T query(idx_t l, idx_t r) { // l <= r
- int i = h_bit(r - l + 1ul);
- return min(a[i][l], a[i][r+1-(1<<i)], Compare());
- }
- };
- using poly = vector<int>;
- void bit_reverse_swap(vector<int> &a) {
- int n = SZ(a);
- for (int i = 1, j = n >> 1, k; i < n - 1; i++) {
- if (i < j) swap(a[i], a[j]);
- //tricky
- for (k = n >> 1; j >= k; j -= k, k >>= 1); //inspect the highest "1"
- j += k;
- }
- }
- void FFT(vector<int> &a, int type) {
- bit_reverse_swap(a);
- int n = SZ(a);
- for (int i = 2; i <= n; i *= 2) {
- const auto wi = fp(3, type * (mod - 1) / i); // i次单位根
- for (int j = 0; j < n; j += i) {
- auto w(1);
- for (int k = j, h = i >> 1; k < j + h; k++) {
- auto t = Mul(w, a[k + h]), u = a[k];
- a[k] = Add(u, t);
- a[k + h] = Sub(u, t);
- mul(w, wi);
- }
- }
- }
- const int inv = fp(n, -1);
- if (type == -1) for (auto &x : a) mul(x, inv);
- }
- void fp(poly &a, const int n) {
- a.resize((ul)pow2((SZ(a)-1) * n + 1));
- FFT(a, 1);
- for(auto &x: a) x = fp(x, n);
- FFT(a, -1);
- }
- // DEBUG code by tourist
- string to_string(string s) {
- return '"' + s + '"';
- }
- string to_string(const char* s) {
- return to_string((string) s);
- }
- string to_string(bool b) {
- return (b ? "true" : "false");
- }
- template <typename A, typename B>
- string to_string(pair<A, B> p) {
- return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
- }
- template <typename A>
- string to_string(A v) {
- bool first = true;
- string res = "{";
- for (const auto &x : v) {
- if (!first) {
- res += ", ";
- }
- first = false;
- res += to_string(x);
- }
- res += "}";
- return res;
- }
- void debug_out() { cerr << endl; }
- template <typename Head, typename... Tail>
- void debug_out(Head H, Tail... T) {
- cerr << " " << to_string(H);
- debug_out(T...);
- }
- #ifdef LOCAL
- #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
- #else
- #define debug(...) 42
- #endif
- // end DEBUG
- //////////////////*^"^*/////////////////////////////////////
- const int N = 1e5+5, M = 1005;
- struct arc {
- int to, next;
- int cap, cost;
- };
- const int nax = 2505;
- vi head(nax, -1);
- vector<arc> e;
- void add_edge(int u, int v, int cap, int cost) {
- e.pb({v, head[u], cap, cost});
- head[u] = SZ(e) - 1;
- e.pb({u, head[v], 0, -cost});
- head[v] = SZ(e) - 1;
- }
- int d[nax];
- const int inf = 100;
- bool dijkstra(int s, int t) {
- pq<pii, greater<pii>> que;
- fill(all(d), inf);
- que.push({d[s] = 0, s});
- while (!que.empty()) {
- auto top = que.top();
- que.pop();
- int u = top.second;
- if (d[u] != top.first) continue;
- for (int i = head[u]; i != -1; i = e[i].next) {
- int v = e[i].to;
- if (e[i].cap > 0 && d[v] > d[u] + e[i].cost) {
- d[v] = d[u] + e[i].cost;
- que.push({d[v], v});
- }
- }
- }
- return d[t] < inf;
- }
- vi cur(nax);
- vb vis(nax);
- int dfs(int u, int flow, int t) {
- if (u == t) return flow;
- vis[u] = true; // "vis[u] = true;" 不能写在 "if (u == t) return flow;" 之前!
- int pushed = 0;
- for (int &i = cur[u]; i != -1; i = e[i].next) {
- int v = e[i].to;
- if (!vis[v] && e[i].cap && d[v] == d[u] + e[i].cost) {
- int tmp = dfs(v, min(flow - pushed, e[i].cap), t);
- if (tmp) {
- e[i].cap -= tmp;
- e[i ^ 1].cap += tmp;
- pushed += tmp;
- if (flow == pushed) break;
- }
- }
- }
- vis[u] = false;
- return pushed;
- }
- ll mcmf(int s, int t) {
- ll ans = 0;
- while (dijkstra(s, t)) {
- cur = head;
- while (true) {
- int f = dfs(s, INT_MAX, t);
- if (f) ans += f * d[t];
- else break;
- }
- }
- return ans;
- }
- int main() {
- FAST_READ
- #ifdef LOCAL
- ifstream in("main.in");
- cin.rdbuf(in.rdbuf());
- #endif
- int n, m; scan(n, m);
- vv<int> h(n, vi(m));
- int tot = 0;
- For (row, h) For(x, row) scan(x), tot += x;
- int tar = tot / (n * m);
- const int dx[]={0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
- int s = n * m, t = s + 1;
- rng (i, 0, n) rng (j, 0, m) {
- int u = i * m + j;
- if (h[i][j] > tar) {
- add_edge(s, u, h[i][j] - tar, 0);
- }
- if (h[i][j] < tar) {
- add_edge(u, t, tar - h[i][j], 0);
- }
- rng (k, 0, 4) {
- int ni = i + dx[k], nj = j + dy[k];
- if(bet(0, n-1, ni) && bet(0, m-1, nj)) {
- add_edge(u, ni * m + nj, INT_MAX, 1);
- }
- }
- }
- dijkstra(s, t);
- println(mcmf(s, t));
- #ifdef LOCAL
- cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement