CF1131D Gourmet choice

题目链接

题意

有两组菜，第一组有\(n\)种，第二组有\(m\)种。给出一个\(n\times 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;
}