Blog of RuSun

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

CF802N April Fools' Problem (medium)

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

LuoGu: CF802N April Fools’ Problem (medium)

CF: N. April Fools’ Problem (medium)

给定两个长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n $和 $b_1, b_2, \ldots b_n$。要求选出 $i_1, i_2, \ldots, i_k $和 $j_1, j_2, \ldots, j_k$，满足

  • $1< i_1< i_2<\ldots< i_k$，$1< j_1< j_2<\ldots< j_k$。
  • $i_p\leq j_p$（$1\leq p \leq k$）。

最小化 $\sum_{p=1}^k a_{i_p}+b_{j_p}$ 的值。

答案为 $k$ 个 $a _ i$ 和 $k$ 个 $b _ i$ ，那么可以看作 $a _ {p1 _ i}$ 和 $b _ {p2 _ i}$ 是一个匹配，满足 $p1 _ 1 \le p2 _ i$ 。那么每一个 $a _ i$ 可以向后面的 $b _ i$ 匹配。求 $k$ 个匹配的最小代价，费用流即可。

考虑这样做的正确性，可能出现一种情况，如 $a _ 1$ 和 $b _ 5$ 匹配了，$a _ 2$ 和 $b _ 4$ 匹配了，没有满足第一个条件。出现这一种情况的时候，一定可以调换其位置使其满足条件。这样做的空间复杂度为 $O(n ^ 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
#include <cstdio>
#include <queue>
using namespace std;
typedef long long LL;
const LL inf = 1e16;
const int N = 5e3 + 10, M = 1e7 + 10;
bool vis[N];
LL d[N];
int n, m, A[N], B[N], st, ed, pre[N], incf[N];
int idx = -1, hd[N], nxt[M], edg[M], wt[M], f[M];
bool spfa()
{
    for (int i = st; i <= ed; i++)
        d[i] = inf;
    for (int i = st; i <= ed; i++)
        incf[i] = 0;
    d[st] = 0;
    incf[st] = n;
    queue<int> q;
    q.push(st);
    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 (d[t] + f[i] < d[edg[i]] && wt[i])
            {
                d[edg[i]] = d[t] + f[i];
                pre[edg[i]] = i;
                incf[edg[i]] = min(wt[i], incf[t]);
                if (!vis[edg[i]])
                {
                    q.push(edg[i]);
                    vis[edg[i]] = true;
                }
            }
    }
    return incf[ed] > 0;
}
LL ek()
{
    LL res = 0;
    while (spfa())
    {
        int t = incf[ed];
        res += t * d[ed];
        for (int i = ed; i != st; i = edg[pre[i] ^ 1])
        {
            wt[pre[i]] -= t;
            wt[pre[i] ^ 1] += t;
        }
    }
    return res;
}
void add(int a, int b, int c, int d)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
    wt[idx] = c;
    f[idx] = d;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &B[i]);
    st = 0, ed = n * 2 + 2;
    for (int i = st; i <= ed; i++)
        hd[i] = -1;
    add(st, ed - 1, m, 0);
    add(ed - 1, st, 0, 0);
    for (int i = 1; i <= n; i++)
    {
        add(ed - 1, i, 1, 0);
        add(i, ed - 1, 0, 0);
    }
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
        {
            add(i, j + n, 1, A[i] + B[j]);
            add(j + n, i, 0, -A[i] - B[j]);
        }
    for (int i = n + 1; i <= n * 2; i++)
    {
        add(i, ed, 1, 0);
        add(ed, i, 0, 0);
    }
    printf("%lld", ek());
    return 0;
}

考虑建图的优化，$1$ 号点要向 $n + 1, n + 2, \ldots, n + n$ 连边， $2$ 号点要向 $n + 2, n + 3, \ldots, n + n$ 连边，其中很多都是重复的，考虑优化。

  • 对于每个点，源点向其连边，流量为 $1$ ，代价为 $A _ i$ ；其向汇点连边，流量为 $1$ ，代价为 $B _ i$ ；
  • 对于每个点，向下一个点连边，流量为 $inf$ 。
  • 处理一下 $k$ 组匹配。
查看代码 
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
#include <cstdio>
#include <queue>
using namespace std;
typedef long long LL;
const LL inf = 1e16;
const int N = 3e3 + 10, M = 2e4 + 10;
bool vis[N];
LL d[N];
int n, m, A[N], B[N], st, ed, pre[N], incf[N];
int idx = -1, hd[N], nxt[M], edg[M], wt[M], f[M];
bool spfa()
{
    for (int i = st; i <= ed; i++)
        d[i] = inf;
    for (int i = st; i <= ed; i++)
        incf[i] = 0;
    d[st] = 0;
    incf[st] = n;
    queue<int> q;
    q.push(st);
    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 (d[t] + f[i] < d[edg[i]] && wt[i])
            {
                d[edg[i]] = d[t] + f[i];
                pre[edg[i]] = i;
                incf[edg[i]] = min(wt[i], incf[t]);
                if (!vis[edg[i]])
                {
                    q.push(edg[i]);
                    vis[edg[i]] = true;
                }
            }
    }
    return incf[ed] > 0;
}
LL ek()
{
    LL res = 0;
    while (spfa())
    {
        int t = incf[ed];
        res += t * d[ed];
        for (int i = ed; i != st; i = edg[pre[i] ^ 1])
        {
            wt[pre[i]] -= t;
            wt[pre[i] ^ 1] += t;
        }
    }
    return res;
}
void add(int a, int b, int c, int d)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
    wt[idx] = c;
    f[idx] = d;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &B[i]);
    st = 0, ed = n + 2;
    for (int i = st; i <= ed; i++)
        hd[i] = -1;
    add(st, ed - 1, m, 0);
    add(ed - 1, st, 0, 0);
    for (int i = 1; i <= n; i++)
    {
        add(ed - 1, i, 1, A[i]);
        add(i, ed - 1, 0, -A[i]);
        add(i, ed, 1, B[i]);
        add(ed, i, 0, -B[i]);
    }
    for (int i = 1; i < n; i++)
    {
        add(i, i + 1, n, 0);
        add(i + 1, i, 0, 0);
    }
    printf("%lld", ek());
    return 0;
}

此题还有 hard 版本 CF802O 。

相关文章