题目链接

题意

有两组菜，第一组有(n)种，第二组有(m)种。给出一个(ntimes m)的矩阵，第(i)行第(j)列表示第一组中的第(i)种菜与第二组中的第(j)种菜好吃程度的比较。
如果为('>')表示第一组中的第(i)种菜比第二组种的第(j)种菜更好吃。
如果为('<')，表示第二组种的第(j)种菜比第一组中的第(i)种菜更好吃。
如果为('=')，表示两种菜同样好吃。
现在要给每种菜打上一个评分，要求好吃的菜的评分一定要比不好吃的更高。同样好吃的两种菜评分要相同。
第一行输出("yes")表示可以完成。并在下面两行分别输出两组菜的评分。
如果无法完成，输出一行"no"

思路

并查集+拓扑排序
首先把所有的相等的菜放到一个并查集里面去。
然后从不好吃的菜向好吃的连边。然后开始拓扑排序。
对于每道菜，比他更好吃的菜的评分都是他的评分(+1)，如果无法拓扑，说明存在环，输出("no")即可。

代码

#include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<algorithm> #include<cstring> #include<queue> #include<bitset> using namespace std; typedef long long ll; const int n = 3010; ll read() {     ll x=0,f=1;char c=getchar();     while(c<'0'||c>'9') {         if(c=='-') f=-1;         c=getchar();     }     while(c>='0'&&c<='9') {         x=x*10+c-'0';         c=getchar();     }     return x*f; } char s[n][n]; int vis[n],ans[n]; queue<int>q; struct node {     int v,nxt; }e[n * n]; int fa[n]; int head[n],ejs; void add(int u,int v) {     e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs; } int du[n]; int find(int x) {     return fa[x] == x ? x : fa[x] = find(fa[x]); } void uni(int x,int y) {     x = find(x),y = find(y);     if(rand() & 1) swap(x,y);     fa[x] = y; } int main() {     int n = read(),m = read();     for(int i = 1;i <= n + m;++i) fa[i] = i;     for(int i = 1;i <= n;++i) {         scanf("%s",s[i] + 1);         for(int j = 1;j <= m;++j) {             if(s[i][j] == '=') uni(i,j + n);         }     }     for(int i = 1;i <= n;++i) {         for(int j = 1;j <= m;++j) {             int x = find(i),y = find(j + n);             if(s[i][j] == '<') {                 if(x == y) {                     puts("no");                     return 0;                 }                 add(x,y);                 du[y]++;             }             else if(s[i][j] == '>') {                 if(x == y) {                     puts("no");return 0;                 }                 add(y,x);                 du[x]++;             }         }     }     int tot = 0;     for(int i = 1;i <= n + m;++i) {         int x = find(i);if(vis[x]) continue;         tot++;         vis[x] = 1;         if(!du[x]) q.push(x),ans[x] = 1;     }     while(!q.empty()) {         int u = q.front();q.pop();tot--;         for(int i = head[u];i;i = e[i].nxt) {             int v = e[i].v;du[v]--;             if(!du[v]) q.push(v),ans[v] = ans[u] + 1;         }     }     if(tot) {         puts("no");return 0;     }     puts("yes");     for(int i = 1;i <= n;++i)         printf("%d ",ans[find(i)]);     puts("");     for(int i = 1;i <= m;++i)         printf("%d ",ans[find(i + n)]);     return 0; }