P1650 田忌赛马

DAMDAM · 2024-09-12 20:10:17 · 题解

你说得对但是我是 2B 不会贪心。

考虑跑网络流。这是一个二分图最大权匹配可以费用流搞搞。

跑最大费用最大流即可（边权已经在上方取反）。

但是这个建图是 n^2 的。。。

看到权值被分为 3 部分，我们可以考虑排序双指针后线段树优化建图。具体地说，我们将原来的齐王马 j 变成树上的一个叶子，建一棵入树，树上的边父亲到儿子边权 0 限制 \infin。

那么排序后用双指针对于每个田忌马分成 3 个区间后可以直接连向齐王马。这样做的话效率就对了。

#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/priority_queue.hpp>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 2e3 + 5;
const int maxVertex = 8e3 + 5, maxEdge = 5e5 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct Vertex {
    int num;
    ll dis;
    bool operator<(const Vertex &b) const & {
        return dis > b.dis;
    }
};

struct Edge {
    int to;
    ll dis, flow;
    int next;
} edge[maxEdge << 1];

int head[maxVertex];
void insert(const int &u, const int &v, const ll &w, const ll &c) {
    static int len = 1;
    edge[++len] = {v, w, c, head[u]}, head[u] = len;
}

void emplace(const int &u, const int &v, const ll &w, const ll &c) {
    insert(u, v, w, c), insert(v, u, -w, 0);
}

int s, t, cur[maxVertex];
ll dis[maxVertex], w[maxVertex], reply;
queue<int> q;
bitset<maxVertex> vis;
void Bellman_Ford() {
    q.push(s), memset(w, 63, sizeof w), w[s] = 0, vis[s] = 1;
    for (int u, v; !q.empty(); ) {
        u = q.front(), q.pop(), vis[u] = 0;
        for (int i = head[u]; i; i = edge[i].next) {
            if (edge[i].flow && w[v = edge[i].to] > w[u] + edge[i].dis)
                w[v] = w[u] + edge[i].dis, vis[v] || (q.push(v), vis[v] = 1);
        }
    }
} 

priority_queue<Vertex> h;
bool Dijkstra() {
    memset(dis, 63, sizeof dis), h.push({s, dis[s] = 0});
    ll d;
    for (int u, v; !h.empty(); ) {
        u = h.top().num, h.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = edge[i].next) {
            v = edge[i].to;
            if (edge[i].flow && dis[v] > (d = dis[u] + w[u] - w[v] + edge[i].dis))
                h.push({v, dis[v] = d});
        }
    }
    return dis[t] != inf;
}

ll Dfs(const int &u, const ll &flow) {
    if (u == t || !flow) return flow;
    ll ans = 0, d;
    vis[u] = 1;
    for (int &i = cur[u], v; i; i = edge[i].next) {
        v = edge[i].to;
        if (!vis[v] && dis[v] == dis[u] + w[u] - w[v] + edge[i].dis && (d = Dfs(v, min(edge[i].flow, flow - ans)))) {
            edge[i].flow -= d, edge[i ^ 1].flow += d, reply += d * edge[i].dis;
            if ((ans += d) == flow) break;
        }
    }
    return vis[u] = 0, ans;
}

void init() { for (int i = 0; i < maxVertex; ++i) w[i] += dis[i]; }

ll Dinic() {
    ll flow = 0;
    for (Bellman_Ford(); Dijkstra(); memcpy(cur, head, sizeof cur), vis.reset(), flow += Dfs(s, inf), init()) ;
    return flow;
}

int a[maxn], b[maxn], n, len, rt, ls[maxVertex], rs[maxVertex];
void Build(const int &l = 1, const int &r = n, int &p = rt) {
    p || (p = ++len);
    if (l == r) return emplace(p, t, 0, 1);
    int mid = l + ((r - l) >> 1);
    Build(l, mid, ls[p]), Build(mid + 1, r, rs[p]);
    emplace(p, ls[p], 0, inf), emplace(p, rs[p], 0, inf);
}

void Point2Range(const int &l, const int &r, const int &u, const ll &w, const ll &c, const int &s = 1, const int &t = n, const int &p = rt) {
    if (l <= s && t <= r) return emplace(u, p, w, c);
    int mid = s + ((t - s) >> 1);
    if (l <= mid) Point2Range(l, r, u, w, c, s, mid, ls[p]);
    if (r > mid) Point2Range(l, r, u, w, c, mid + 1, t, rs[p]);
}

int main() {
    scanf("%d", &n), s = ++len, t = ++len;
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), emplace(s, ++len, 0, 1);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) scanf("%d", b + i);
    sort(b + 1, b + n + 1), Build();
    for (int i = 1, j = 1, k = 1; i <= n; ++i) {
        for (; j <= n && b[j] < a[i]; ++j) ;
        for (; k <= n && b[k] <= a[i]; ++k) ;
        if (j > 1) Point2Range(1, j - 1, i + 2, -200, 1);
        if (j <= n && j < k) Point2Range(j, k - 1, i + 2, 0, 1);
        if (k <= n) Point2Range(k, n, i + 2, 200, 1);
    }
    Dinic(), printf("%lld", -reply);
    return 0;
}