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; }
上一篇: 浅谈 Virtual DOM 的那些事
下一篇: Redis Cluster [WARNING] Node 127.0.0.1:7003 has slots in migrating state (15495).
推荐阅读
-
台北电脑展Best Choice Award出炉 7nm锐龙要拿年度大奖?
-
numpy.random.choice
-
CF1131D Gourmet choice
-
Python中的choice()方法使用详解
-
python从入门到放弃篇15.1(列表list,random.randint,random.choice,if嵌套)实现四则运算的猜数小游戏v2.0版
-
Duke's Choice Award 2009(译)
-
Duke's Choice Award 2009(译)
-
windows xp下没有dos的choice命令的解决方法
-
dos命令行choice命令使用详解
-
2005 LinuxQuestions.org Members Choice Awards的一些结果