Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

CF730I Olympiad in Programming and Sports

发表于 分类于
本文字数： 7.7k 阅读时长 ≈ 7 分钟
标签：        

LuoGu: CF730I Olympiad in Programming and Sports

CF: I. Olympiad in Programming and Sports

二分图的多重带权匹配，直接上板子。

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <cstdio>
#include <queue>
using namespace std;
typedef pair <int, int> PII;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 3e3 + 10, M = 24e3 + 10, inf = 9e3;
bool vis[N];
int n, p, q, st, ed, h[N], d[N], pre[N];
int idx = -1, hd[N], nxt[M], edg[M], wt[M], cst[M];
void add (int a, int b, int c, int d)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
    wt[idx] = c;
    cst[idx] = d;
}
void spfa ()
{
    for (int i = 1; i <= n; i++)
        h[i] = -inf;
    queue <int> q;
    q.push(st);
    h[st] = 0;
    vis[st] = true;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        vis[t] = false;
        for (int i = hd[t]; ~i; i = nxt[i])
            if (wt[i] && h[t] + cst[i] > h[edg[i]])
            {
                h[edg[i]] = h[t] + cst[i];
                if (!vis[edg[i]])
                {
                    vis[edg[i]] = true;
                    q.push(edg[i]);
                }
            }
    }
}
bool dijkstra ()
{
    for (int i = 1; i <= n; i++)
        vis[i] = false, d[i] = -inf;
    priority_queue <PII> q;
    d[st] = 0;
    q.push(make_pair(0, st));
    while (!q.empty())
    {
        int t = q.top().second;
        q.pop();
        if (vis[t])
            continue;
        vis[t] = true;
        for (int i = hd[t]; ~i; i = nxt[i])
            if (wt[i] && d[t] + cst[i] + h[t] - h[edg[i]] > d[edg[i]])
            {
                d[edg[i]] = d[t] + cst[i] + h[t] - h[edg[i]];
                pre[edg[i]] = i;
                q.push(make_pair(d[edg[i]], edg[i]));
            }
    }
    return d[ed] ^ -inf;
}
int PrimalDual ()
{
    spfa();
    int res = 0;
    while (dijkstra())
    {
        for (int i = 1; i <= n; i++)
            h[i] += d[i];
        int t = inf;
        for (int i = ed; i ^ st; i = edg[pre[i] ^ 1])
            t = min(t, wt[pre[i]]);
        for (int i = ed; i ^ st; i = edg[pre[i] ^ 1])
            wt[pre[i]] -= t, wt[pre[i] ^ 1] += t;
        res += t * h[ed];
    }
    return res;
} 
int main ()
{
    read(n), read(p), read(q);
    st = n + 1, ed = n + 4;
    for (int i = 1; i <= n + 4; i++)
        hd[i] = -1;
    for (int i = 1; i <= n; i++)
    {
        add(st, i, 1, 0);
        add(i, st, 0, 0);
    }
    for (int i = 1, a; i <= n; i++)
    {
        read(a);
        add(i, n + 2, 1, a);
        add(n + 2, i, 0, -a);
    }
    for (int i = 1, a; i <= n; i++)
    {
        read(a);
        add(i, n + 3, 1, a);
        add(n + 3, i, 0, -a);
    }
    add(n + 2, ed, p, 0);
    add(ed, n + 2, 0, 0);
    add(n + 3, ed, q, 0);
    add(ed, n + 3, 0, 0);
    n += 4;
    write(PrimalDual()), puts("");
    for (int i = hd[n - 2]; ~i; i = nxt[i])
        edg[i] ^ n && wt[i] && (write(edg[i]), putchar(' '));
    puts("");
    for (int i = hd[n - 1]; ~i; i = nxt[i])
        edg[i] ^ n && wt[i] && (write(edg[i]), putchar(' '));
    return 0;
}

进一步发现可以模拟费用流，每一次增广可能的操作有四种：

  • 将没有选择的加入集合 $1$ ；
  • 将没有选择的加入集合 $2$ ；
  • 将一个没有选择的加入集合 $2$ ，将集合 $2$ 中的一个加入集合 $1$ ；
  • 将一个没有选择的加入集合 $1$ ，将集合 $1$ 中的一个加入集合 $2$ 。

用四个堆维护四种操作的价值，每次增广选择最大的即可。

堆中可以使用懒惰删除。

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <cstdio>
#include <queue>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 3e3 + 10, inf = 9e6;
int n, p, q, w[N], v[N], match[N];
struct Data
{
    int v, id;
    bool operator < (const Data &_) const
    {
        return v < _.v;
    }
};
priority_queue <Data> q01, q02, q12, q21;
void chkmax (int k, int t, int &del, int &op)
{
    k > del && (del = k, op = t);
}
int main ()
{
    read(n), read(p), read(q);
    for (int i = 1; i <= n; i++)
        read(w[i]), q01.push((Data){w[i], i});
    for (int i = 1; i <= n; i++)
        read(v[i]), q02.push((Data){v[i], i});
    int res = 0;
    while (p || q)
    {
        int del = -inf, op;
        while (!q01.empty() && match[q01.top().id])
            q01.pop();
        while (!q02.empty() && match[q02.top().id])
            q02.pop();
        while (!q12.empty() && match[q12.top().id] ^ 1)
            q12.pop();
        while (!q21.empty() && match[q21.top().id] ^ 2)
            q21.pop();
        if (p)
        {
            if (!q01.empty())
                chkmax(q01.top().v, 1, del, op);
            if (!q02.empty() && !q21.empty())
                chkmax(q02.top().v + q21.top().v, 2, del, op);
        }
        if (q)
        {
            if (!q02.empty())
                chkmax(q02.top().v, 3, del, op);
            if (!q01.empty() && !q12.empty())
                chkmax(q01.top().v + q12.top().v, 4, del, op);
        }
        res += del;
        if (op == 1)
        {
            int t = q01.top().id;
            q12.push((Data){v[t] - w[t], t}), match[t] = 1;
            p--;
        }
        else if (op == 2)
        {
            int a = q02.top().id, b = q21.top().id;
            q21.push((Data){w[a] - v[a], a}), match[a] = 2;
            q12.push((Data){v[b] - w[b], b}), match[b] = 1;
            p--;
        }
        else if (op == 3)
        {
            int t = q02.top().id;
            q21.push((Data){w[t] - v[t], t}), match[t] = 2;
            q--;
        }
        else if (op == 4)
        {
            int a = q01.top().id, b = q12.top().id;
            q12.push((Data){v[a] - w[a], a}), match[a] = 1;
            q21.push((Data){w[b] - v[b], b}), match[b] = 2;
            q--;
        }
    }
    write(res), puts("");
    for (int i = 1; i <= n; i++)
        match[i] == 1 && (write(i), putchar(' '));
    puts("");
    for (int i = 1; i <= n; i++)
        match[i] == 2 && (write(i), putchar(' '));
    return 0;
}
相关文章