QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#425783#6104. Building BombingHKOI0#WA 1ms3828kbC++204.5kb2024-05-30 16:55:012024-05-30 16:55:02

Judging History

你现在查看的是最新测评结果

  • [2024-05-30 16:55:02]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3828kb
  • [2024-05-30 16:55:01]
  • 提交

answer

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define int long long
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const ll INF = numeric_limits<ll>::max() / 4;

struct MCMF {
    struct edge {
        int from, to, rev;
        ll cap, cost, flow;
    };
    int N;
    vector<vector<edge>> ed;
    vi seen;
    vector<ll> dist, pi;
    vector<edge*> par;

    MCMF(int N): N(N), ed(N), seen(N), dist(N), pi(N), par(N) {}

    void addEdge(int from, int to, ll cap, ll cost) {
        if (from == to) return;
        ed[from].push_back(edge{ from,to,sz(ed[to]),cap,cost,0 });
        ed[to].push_back(edge{ to,from,sz(ed[from])-1,0,-cost,0 });
    }

    void path(int s) {
        fill(all(seen), 0);
        fill(all(dist), INF);
        dist[s] = 0; ll di;

        __gnu_pbds::priority_queue<pair<ll, int>> q;   
        vector<decltype(q)::point_iterator> its(N);
        q.push({ 0, s });

        while (!q.empty()) {
            s = q.top().second; q.pop();
            seen[s] = 1; di = dist[s] + pi[s];
            for (edge& e : ed[s]) if (!seen[e.to]) {
                ll val = di - pi[e.to] + e.cost;
                if (e.cap - e.flow > 0 && val < dist[e.to]) {
                    dist[e.to] = val;
                    par[e.to] = &e;
                    if (its[e.to] == q.end())
                        its[e.to] = q.push({ -dist[e.to], e.to });
                    else
                        q.modify(its[e.to], { -dist[e.to], e.to });
                }
            }
            for (int i = 0; i < N; i++)
                pi[i] = min(pi[i] + dist[i], INF);
        }
    }

    pair<ll, ll> maxflow(int s, int t) {
        ll totflow = 0, totcost = 0;
        while (path(s), seen[t]) {
            ll fl = INF;
            for (edge* x = par[t]; x; x = par[x->from])
                fl = min(fl, x->cap - x->flow);

            totflow += fl;
            for (edge* x = par[t]; x; x = par[x->from]) {
                x->flow += fl;
                ed[x->to][x->rev].flow -= fl;
            }
        }
        for (int i = 0; i < N; i++) for (edge& e : ed[i]) totcost += e.cost * e.flow;
        return {totflow, totcost/2};
    }

    void setpi(int s) {
        fill(all(pi), INF); pi[s] = 0;
        int it = N, ch = 1; ll v;
        while (ch-- && it--)
            for (int i = 0; i < N; i++) if (pi[i] != INF)
                for (edge& e : ed[i]) if (e.cap)
                    if ((v = pi[i] + e.cost) < pi[e.to])
                        pi[e.to] = v, ch = 1;
        assert(it >= 0);
    }
};

void solve() {
    int n,m; cin >> n >> m;
    vector<vector<int>> p(n, vector<int>(m, 0)), w = p;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> p[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> w[i][j];

    const int SRC = 3 * n * m;
    const int SINK = 3 * n * m + 1;
    const int HORI_BASE = n * m;
    const int VERT_BASE = 2 * n * m;
    MCMF mcmf(3 * n * m + 2);

    // ROOM
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            mcmf.addEdge(SRC, i * m + j, 4 - w[i][j], 0);

    ll totalDiscomfort = 0;

    // HORI
    for (int i = 0; i < n; i++)
        for (int j = 0; j + 1 < m; j++) {
            const int room1 = i * m + j;
            const int room2 = i * m + (j + 1);
            const int edge = HORI_BASE + room1;

            totalDiscomfort += p[i][j] * p[i][j + 1];

            mcmf.addEdge(room1, edge, 1, 0);
            mcmf.addEdge(room2, edge, 1, 0);
            mcmf.addEdge(edge, SINK, 1, -p[i][j] * p[i][j + 1]);
        }

    // VERT
    for (int i = 0; i + 1 < n; i++)
        for (int j = 0; j < m; j++) {
            const int room1 = i * m + j;
            const int room2 = (i + 1) * m + j;
            const int edge = VERT_BASE + room1;

            totalDiscomfort += p[i][j] * p[i + 1][j];

            mcmf.addEdge(room1, edge, 1, 0);
            mcmf.addEdge(room2, edge, 1, 0);
            mcmf.addEdge(edge, SINK, 1, -p[i][j] * p[i + 1][j]);
        }

    const ll maxcost = -mcmf.maxflow(SRC, SINK).second;
    cout << totalDiscomfort << ' ' << maxcost << '\n';
    cout << totalDiscomfort - maxcost << '\n';
}

signed main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3828kb

input:

7 2 3
10 30 90 40 60 60 80

output:

24720 24720
0

result:

wrong answer 1st numbers differ - expected: '2', found: '24720'