P8186 题解

· · 题解

感谢 @Autumn_0930 指出文中错误，现已修复。

1.题意简述

有 n 头牛和 n 个礼物，编号为 1,2,3,...,n，初始时每头牛都分到了与它编号相同的礼物。

奶牛们对所有礼物的喜爱程度都有一个排序，且它们想重新分配礼物。如果存在另一种分配方式，使得每头牛都能得到当前的礼物或比它更好的礼物，则它们可能会采用这种方式。

求每头牛可能得到的对它来说最好的礼物。

2.样例分析

首先看一组样例：

5
5 4 3 2 1
1 2 5 4 3
2 3 4 1 5
5 1 4 2 3
4 5 2 1 3

输出为：

5
1
2
5
4

用礼物的编号来表示分配方式。 如 1,5,4,2,3 代表 1 号牛拿到了 1 号礼物，2 号牛拿到了 5 号礼物，以此类推。

这组样例中的合法方案有：

5 2 3 1 4
3 1 2 5 4

这两种方案就足以得出答案。方案 1 中，1,4,5 号牛交换了礼物，方案 2 中，1,2,3 号牛交换了礼物，而它们都是以轮换的方式交换礼物（如我的给你，你的给他，他的给我）。因此，我们可以想到 Floyd 求任意两点连通性（传递闭包）。

3.做法分析

该题中无需分析最短路，所以只需判环即可。

首先建图：若一头奶牛认为另一头奶牛的礼物比它的好，则该奶牛对应的点向另一头奶牛对应的点连一条有向边。

for (int i=1,a;i<=n;i++) for (int j=1;j<=n;j++){
    cin>>a;
    if (a==i) {
        for (j++;j<=n;j++) cin>>a;break;
//后面的礼物没有原来的好，直接忽略
    }
    d[i][a]=1;
    to[i].push_back(a);
}

接下来的判环略有难度。常规的判环都是将 d_{i,i} 初始化为 0 后跑 Floyd 算法，最后判断 d_{i,i} 是否为 1，然而本题中可能有多个环，为了同时判断礼物的来源，应修改为判断 d_{i,j} 和 d_{j,i} 同时为 1。

for (int i=1,fl;i<=n;i++){
    fl=0;
    for (int j=0;j<to[i].size();j++){
        if (d[to[i][j]][i]){
            cout<<to[i][j]<<endl;fl=1;break;
//找到了环，获得新礼物
        }
    }
    if (!fl) cout<<i<<endl; //没有环，保留原来的礼物
}

把它们连在一起就得到了完整代码。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int d[507][507],n;
vector<int> to[507];
//to[i]记录比i号牛原来的礼物好的礼物
int main(){
    cin>>n;
    for (int i=1,a;i<=n;i++) for (int j=1;j<=n;j++){
        cin>>a;
        if (a==i) {
            for (j++;j<=n;j++) cin>>a;break;
//后面的礼物没有原来的好，直接忽略
        }
        d[i][a]=1;to[i].push_back(a);
    }
    for (int k=1;k<=n;k++) 
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                d[i][j]|=(d[i][k]&&d[k][j]);
//Floyd
    for (int i=1,fl;i<=n;i++){
        fl=0;
        for (int j=0;j<to[i].size();j++){
            if (d[to[i][j]][i]){
                cout<<to[i][j]<<endl;fl=1;break;
//找到了环，获得新礼物
            }
        }
        if (!fl) cout<<i<<endl; //没有环，保留原来的礼物
    }
    return 0;
}