Redistributing Gifts

题意

有 $N$ 头奶牛和 $N$ 个礼物。初始时，第 $i$ 头奶牛拿到第 $i$ 个礼物。

每头奶牛给出一个礼物偏好排列。奶牛们可以重新分配礼物，但每头奶牛最终拿到的礼物必须不比自己原来的礼物更差。

对每头奶牛，输出她在某种合法重新分配中可能拿到的最喜欢的礼物。

思路

先看一个小数据暴力。它枚举所有礼物分配排列，保留每头奶牛都不变差的方案，再统计每头奶牛能拿到的最优礼物。

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 19:23
 * update_at: 2026-07-11 19:25
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 12;

int n;
int pref[MAXN][MAXN];
int rank_pos[MAXN][MAXN]; // rank_pos[i][gift] 越小表示奶牛 i 越喜欢
int perm_gift[MAXN];
int best_gift[MAXN];

void check_perm() {
    for (int i = 1; i <= n; i++) {
        if (rank_pos[i][perm_gift[i]] > rank_pos[i][i]) {
            return;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (rank_pos[i][perm_gift[i]] < rank_pos[i][best_gift[i]]) {
            best_gift[i] = perm_gift[i];
        }
    }
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> pref[i][j];
            rank_pos[i][pref[i][j]] = j;
        }
        best_gift[i] = i;
    }

    for (int i = 1; i <= n; i++) {
        perm_gift[i] = i;
    }

    // 小数据暴力：枚举每头牛最终拿到哪个礼物。
    do {
        check_perm();
    } while (next_permutation(perm_gift + 1, perm_gift + n + 1));

    for (int i = 1; i <= n; i++) {
        cout << best_gift[i] << '\n';
    }

    return 0;
}

满分做法把问题转成有向图。

如果奶牛 i 愿意接受礼物 j，就连一条边：

text

1i -> j

这里的礼物 j 也可以看成“原来拥有礼物 j 的奶牛 j”。所以边 i -> j 表示：在某个交换环里，奶牛 i 可以拿走奶牛 j 的礼物。

只连奶牛 i 偏好列表中从开头到礼物 i 为止的礼物，因为这些礼物都不比原来的礼物差。

例如样例中，奶牛 2 可以接受礼物 1,3,2，所以有：

flowchart LR
  C2["cow 2"] --> G1["gift 1"]
  C2 --> G3["gift 3"]
  C2 --> G2["gift 2"]

一次合法的重新分配，本质上是把若干奶牛分成若干个交换环。若奶牛 i 想拿礼物 j，就需要存在一个包含边 i -> j 的环。

在有向图中，边 i -> j 能在某个环里，当且仅当 j 可以沿图走回 i。因此：

text

1奶牛 i 可以拿礼物 j  <=>  reachable[j][i] 为真

于是先用 Floyd 求所有点之间的可达性。因为 $N\leqslant 500$ ，用 bitset 可以把一次合并写成整行或运算：

text

1如果 i 能到 k，那么 i 能到的点并上 k 能到的点

最后对每头奶牛按偏好顺序扫描，找到第一个满足 reachable[gift][i] 的礼物，就是她能拿到的最喜欢礼物。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 19:23
 * update_at: 2026-07-11 19:25
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;

int n;
int pref[MAXN][MAXN]; // pref[i][k] 表示奶牛 i 第 k 喜欢的礼物
bitset<MAXN> reachable[MAXN];

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        bool before_self = true;
        for (int j = 1; j <= n; j++) {
            cin >> pref[i][j];
            if (before_self) {
                reachable[i][pref[i][j]] = true;
            }
            if (pref[i][j] == i) {
                before_self = false;
            }
        }
    }

    // bitset 版 Floyd：如果 i 能到 k，就合并 k 能到的所有点。
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (reachable[i][k]) {
                reachable[i] |= reachable[k];
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int gift = pref[i][j];
            if (reachable[gift][i]) {
                cout << gift << '\n';
                break;
            }
            if (gift == i) {
                break;
            }
        }
    }

    return 0;
}

复杂度

建图需要 $O(N^2)$ 。

bitset Floyd 需要 $O(N^3 / w)$ ，其中 $w$ 是机器字长；在本题 $N\leqslant 500$ 下很轻。

空间复杂度为 $O(N^2)$ 。

总结

本题的关键是把“礼物重新分配”看成交换环。

奶牛 i 能拿礼物 j，等价于边 i -> j 能放进一个环，也就是 j 能到达 i。求出可达闭包后，按偏好顺序选第一个可行礼物即可。

目录

题意

思路

代码

复杂度

总结