本文主要是介绍Codeforces Round #541 (Div. 2)D. Gourmet choice(拓扑排序+并查集+思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://codeforces.com/contest/1131/problem/D
题目大意：给出n个数和m个数之间分别的大小关系，求使得最大数最小的情况
题目思路：如果全是>或者<这道题很简单，直接建图就结束了，但是这里有个=。这个等于的解决非常巧妙，使用并查集将=的点并在一起缩点然后这道题就转换成了只有>或<的情况
以下是代码：
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
const ll MAXN = 2e3+5;
const ll MOD = 1e9+7;
int n,m,a[MAXN],vis[MAXN],pre[MAXN];
vector<int>v[MAXN];
char mp[MAXN][MAXN];
struct node{int x,val;
}p;
queue<node>q;
int Find(int x){return pre[x]==x?x:pre[x]=Find(pre[x]);
}
int main()
{while(~scanf("%d%d",&n,&m)){int flag=0;memset(vis,0,sizeof(vis));memset(a,0,sizeof(a));rep(i,1,n+m)pre[i]=i;rep(i,1,n){scanf("%s",mp[i]+1);}rep(i,1,n){rep(j,1,m){if(mp[i][j]=='='){int xx=Find(i),yy=Find(n+j);pre[xx]=yy;}}}rep(i,1,n){rep(j,1,m){if(mp[i][j]=='=')continue;int xx=Find(i),yy=Find(n+j);if(xx==yy){flag=1;break;}if(mp[i][j]=='<'){v[xx].push_back(yy);vis[yy]++;}if(mp[i][j]=='>'){v[yy].push_back(xx);vis[xx]++;}}if(flag)break;}if(flag){puts("No");continue;}rep(i,1,n){if(vis[i]==0){p.x=i,p.val=1;q.push(p);}}rep(i,1,m){if(vis[n+i]==0){p.x=n+i,p.val=1;q.push(p);}}int tot=0;while(!q.empty()){tot++;p=q.front();q.pop();a[p.x]=p.val;int len=v[p.x].size();rep(i,0,len-1){int to=v[p.x][i];vis[to]--;if(!vis[to]){node temp;temp.x=to,temp.val=p.val+1;q.push(temp);}}}rep(i,1,n+m){a[i]=a[Find(i)];}rep(i,1,n){rep(j,1,m){if((mp[i][j]=='='&&a[i]==a[n+j])||(mp[i][j]=='>'&&a[i]>a[n+j])||(mp[i][j]=='<'&&a[i]<a[n+j]))flag=0;else{flag=1;break;}}if(flag)break;}if(flag)printf("No\n");else{printf("Yes\n");rep(i,1,n+m){printf("%d",a[i]);if(i==n||i==n+m)cout<<endl;else cout<<" ";}}}return 0;
}
这篇关于Codeforces Round #541 (Div. 2)D. Gourmet choice(拓扑排序+并查集+思维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
