题目链接
题意
有两组菜,第一组有(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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605001.html