本文主要是介绍(CodeForces) Codeforces Round #541 (Div. 2) D. Gourmet choice (并查集+拓扑排序)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
题目大意：第一天n个菜，第二天m个菜，一个n*m的矩阵代表他们之间的优劣关系，根据这个矩阵用数字来给每一个菜品打分，使得最大的数字最小。比如 Aij 是> 说明第一天的 i菜 比第二天的 j菜好。
解题思路：根据题目的描述，两道菜之间的优劣情况，我们可以连一条权值为1的单向边，而哪些没有指向他的点，那就是最小的数为1。从入度为0的点开始，一步步往里面走，我们自然可以想到拓扑排序，但这题目还有 = ，说明两个菜的优劣程度相同 那么考虑到，如果两个菜优劣程度相同，其实我们可以将他们认为是一个点(放到一个集合中)，他们满足的条件是共通的，所以我们可以用一个并查集去维护，我们把一个集合里的点都用一个点来代替，然后拓扑就行了，有环说明就矛盾。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
int fa[maxn],rk[maxn];
int n,m;
vector<int> eg[maxn];
void init() {for(int i=0; i<maxn; ++i) {fa[i]=i,rk[i]=1;}
}
int find(int x) {if(x==fa[x]) return fa[x];else return fa[x]=find(fa[x]);
}
void unite(int x,int y) {x=find(x),y=find(y);if(x!=y) {if(rk[x]>rk[y]) fa[y]=x;else {if(rk[x]==rk[y]) rk[y]++;fa[x]=y;}}
}
int in[maxn];
vector<int> num;
int ans[maxn];
void solve() { //拓扑排序int tp,sz=num.size(),cnt=sz;for(int i=0; i<sz; ++i) {for(int j=0; j<(int)eg[num[i]].size(); ++j) {tp=eg[num[i]][j];in[tp]++;}}queue<int> q;for(int i=0; i<sz; ++i) {if(!in[num[i]]) q.push(num[i]),ans[num[i]]=1;}int to;while(!q.empty()) {tp=q.front(),q.pop();cnt--;for(int i=0; i<(int)eg[tp].size(); ++i) {to=eg[tp][i];in[to]--;ans[to]=max(ans[to],ans[tp]+1); //更新ansif(!in[to]) {q.push(to);}}}if(cnt) cout<<"No"<<endl; //说明有环，矛盾else {cout<<"Yes"<<endl;for(int i=1; i<=n; ++i) {cout<<ans[find(i)]<<" ";}cout<<endl;for(int i=1; i<=m; ++i) {cout<<ans[find(i+n)]<<" ";}cout<<endl;}
}
int main() {std::ios::sync_with_stdio(0);init();cin>>n>>m;char tp;for(int i=1; i<=n; ++i) {for(int j=1; j<=m; ++j) {cin>>tp;if(tp=='>') eg[j+n].push_back(i);if(tp=='<') eg[i].push_back(j+n);if(tp=='=') unite(i,j+n);}}for(int i=1; i<=m+n; ++i) { //这一步就是用点来代表集合，这里感觉写繁琐了for(int j=0; j<(int)eg[i].size(); ++j) { //将指出去的边都指向集合的父亲int p=eg[i][j];if(find(p)!=p) eg[i][j]=find(p);}if(find(i)!=i) { //用父亲代表这个集合eg[find(i)].insert(eg[find(i)].end(),eg[i].begin(),eg[i].end());} else num.push_back(i); //现在的点放到num数组中}solve();return 0;
}
这篇关于(CodeForces) Codeforces Round #541 (Div. 2) D. Gourmet choice (并查集+拓扑排序)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
