欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CF1131D Gourmet choice

程序员文章站 2022-03-18 15:42:45
题意 有两组菜,第一组有$n$种,第二组有$m$种。给出一个$n\times m$的矩阵,第$i$行第$j$列表示第一组中的第$i$种菜与第二组中的第$j$种菜好吃程度的比较。 如果为$'>'$表示第一组中的第$i$种菜比第二组种的第$j$种菜更好吃。 ......

题目链接

题意

有两组菜,第一组有\(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;
}