P8186-传递闭包

Redistributing Gifts S

题意简述

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

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

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

即求出每一个一个礼物是否可以通过传递来到某个点，考虑传递闭包

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 5e2+10;
constexpr int INF = LLONG_MAX>>1;int n;
int pos[maxn];         // 拥有礼物的位置
int wi[maxn][maxn];
bitset<maxn> gra[maxn];// bitset 优化 没那么离谱，也就快了一半
int ans[maxn];signed main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endif // ONLINE_JUDGEscanf("%lld",&n);for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){scanf("%lld",&wi[i][j]);if(wi[i][j]==i){pos[i]=j;}}for(int j=1;j<=pos[i];++j){gra[i][wi[i][j]]=1; // 连 i 到期望的礼物}ans[i]=i;// 已经拥有的礼物}for(int k=1;k<=n;++k){for(int i=1;i<=n;++i){if(gra[i][k]){gra[i] |= gra[k];// 优化}}}for(int i=1;i<=n;++i){for(int j=1;j<pos[i];++j){if(gra[wi[i][j]][i])// 存在i期望的礼物能到i{ans[i]=wi[i][j];break;}}}for(int i=1;i<=n;++i){printf("%lld\n",ans[i]);}return 0;
}