P8186 [USACO22FEB] Redistributing Gifts S

题目描述

FJ 有 $N$ 个礼物给他的 $N$ 头奶牛，这 $N$ 个礼物和 $N$ 头奶牛都分别按顺序被标记为从 $1$ 到 $N$ 的整数。每头奶牛都有一个愿望单，记录着一个含有 $N$ 个礼物的排列。比起在愿望单中出现更晚的礼物，奶牛更喜欢先出现在愿望单中的礼物。

因为 FJ 太懒了，他直接把 $i$ 号礼物分配给了 $i$ 号奶牛。现在，奶牛们聚在了一起，决定重新分配礼物，以便在重新分配后，每头奶牛都能得到跟原来一样，或是它更喜欢的礼物。

对于每个 $i$（$1\le i\le N$），计算出重新分配后， $i$ 号奶牛可能拿到的最好的礼物（这个奶牛经过重新分配后能拿到的最喜欢的礼物）。

输入格式

第一行输入 $N$。之后 $N$ 行每行包含一个奶牛的愿望单。保证这 $N$ 行都是从 $1$ 到 $N$ 的排列，即每一行都不按顺序不重不漏地包含 $1$ 到 $N$ 中的每个整数。

输出格式

输出 $N$ 行，第 $i$ 行输出重新分配后 $i$ 号奶牛可能得到的最好礼物。

输入输出样例 #1

输入 #1

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

输出 #1

1
3
2
4

说明/提示

【样例解释】

在这个例子中，有两种可能的分配方案：

• 最初的方案：一号奶牛得到一号礼物，二号奶牛得到二号礼物，三号奶牛得到三号礼物，四号奶牛得到四号礼物。
• 重新分配后的方案：一号奶牛得到一号礼物，二号奶牛得到三号礼物，三号奶牛得到二号礼物，四号奶牛得到四号礼物。可以发现一号和四号奶牛都拿不到比 FJ 分配的更好的礼物，不过二号和三号都可以。

【数据范围】

$2\sim 3$ 号测试点满足 $N\le 8$。

对于 $100\%$ 的数据，满足 $1\le N\le 500$。

C++实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int d[507][507],n;
vector<int> to[507];
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]);
	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;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容