自动搬运

查看原文

来自洛谷，原作者为

	lmh .

搬运于2025-08-24 22:36:43，当前版本为作者最后更新于2022-03-21 15:23:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8186 Redistributing Gifts

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;
}