2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest I Olympiad in Programming and Sports

题目描述

https://codeforces.com/problemset/problem/730/I

简要题意：现在有 $n$ 个人，要将这些人分成两个队伍，每个人只能属于一个队伍，如果将第 $i$ 个人分到第一个队伍，那么能够得到 $a_i$ 的收益，如果将第 $i$ 个人分到第二个队伍，那么将得到 $b_i$ 的收益，第一个队伍有 $p$ 个人，第二个队伍有 $s$，求收益最大的分配方案

$n\le 3000$

Solution

容易得到费用流做法，建图：

$s$ 连 $i$，容量为 $1$，费用为 $0$

$i$ 连 $i_a$，容量为 $1$，费用为 $a_i$

$i$ 连 $i_b$，容量为 $1$，费用为 $b_i$

$i_a$ 连 $t_a$，容量为 $p$，费用为 $0$

$i_b$ 连 $t_b$，容量为 $s$，费用为 $0$

注意到这张图非常简单，我们考虑用堆来对其进行模拟，每次增广只有四种选择，选一个分到第一个队伍，选一个人分到第二个队伍，选一个人分到第一个队伍的同时将一个第一个队伍的人换到第二个队伍，选一个人分到第二队伍的同时，将一个第二队伍的人换到第一个队伍，拿四个堆模拟即可

时间复杂度 $O(n\log n)$

#include <iostream>
#include <queue>
#define maxn 3010
#define INF 1000000000
using namespace std;

int n, A, B, a[maxn], b[maxn];

struct node {
    int k, v;

    friend bool operator < (const node &u, const node &v) { return u.v < v.v; }
};

int use[maxn];
// 1 in A 2 in B

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> A >> B;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    priority_queue<node> qa, qb, qab, qba; int ans = 0; 
    for (int i = 1; i <= n; ++i) qa.push({ i, a[i] }), qb.push({ i, b[i] });
    while (A || B) {
        int v = -INF, op = 0; 
        while (!qa.empty() && use[qa.top().k] != 0) qa.pop();
        while (!qb.empty() && use[qb.top().k] != 0) qb.pop();
        while (!qab.empty() && use[qab.top().k] != 1) qab.pop();
        while (!qba.empty() && use[qba.top().k] != 2) qba.pop();
        if (A) {
            if (!qa.empty() && qa.top().v > v) v = qa.top().v, op = 1;
            if (!qb.empty() && !qba.empty() && qb.top().v + qba.top().v > v) v = qb.top().v + qba.top().v, op = 2;
        }
        if (B) {
            if (!qb.empty() && qb.top().v > v) v = qb.top().v, op = 3;
            if (!qa.empty() && !qab.empty() && qa.top().v + qab.top().v > v) v = qa.top().v + qab.top().v, op = 4;
        } ans += v;
        if (op == 1) {
            int t = qa.top().k; qa.pop(); 
            use[t] = 1; qab.push({ t, b[t] - a[t] });
        } else if (op == 2) {
            int t1 = qb.top().k, t2 = qba.top().k; qb.pop(); qba.pop();
            use[t1] = 2; qba.push({ t1, a[t1] - b[t1] });
            use[t2] = 1; qab.push({ t2, b[t2] - a[t2] });
        } else if (op == 3) {
            int t = qb.top().k; qb.pop();
            use[t] = 2; qba.push({ t, a[t] - b[t] });
        } else {
            int t1 = qa.top().k, t2 = qab.top().k; qa.pop(); qab.pop();
            use[t1] = 1; qab.push({ t1, b[t1] - a[t1] });
            use[t2] = 2; qba.push({ t2, a[t2] - b[t2] });
        }
        if (op <= 2) --A;
        else --B;
    } vector<int> A, B;
    for (int i = 1; i <= n; ++i)
        if (use[i] == 1) A.push_back(i);
        else if (use[i] == 2) B.push_back(i);
    cout << ans << "\n";
    for (auto u : A) cout << u << " "; cout << "\n";
    for (auto u : B) cout << u << " "; cout << "\n";
    return 0;
}