题目大意:

给定n m 第一行有n个数 第二行有m个数

接下来n行每行m列 有 = < >

位于 i j 的符号表示 第一行第i个数与第二行第j个数的大小关系

1.将n+m个数 当做按顺序编号的点

则第二行的数是编号为 n+j 的点

2.先处理=的数 将所有=的数指向同一个父亲

3.再处理不是=的数

找到两者的父亲

如果父亲相同说明两者= 与目前处理的情况相悖 无解

否则 按由小到大的关系在两者(的父亲)间连单向边(小连向大) 此时较大的点入度+1

4.此时查看所有点的入度

入度为0 说明这个点是所有数中最小的数

将它们的答案设为1 放进队列

5.广搜 取出队列里的点

判断是否能去向下一个点 能到的点数值比当前点大

所以 它们的答案 是 当前点的答案+1

6.查看对应点的答案 应该查询 这个点的父亲(数值相等) 的答案

因为连边时 实际上是在对应点的父亲之间连的边

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define mem(i,j) memset(i,j,sizeof(i))
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int N=1e3+;
const int NN=N<<;
const int mod=1e9+; int n, m;
char G[N][N];
int E[NN][NN];
int du[NN], ans[NN];
int fa[NN];
int getfa(int x) {
if(fa[x]==x) return x;
else return fa[x]=getfa(fa[x]);
}
int main()
{
while(~scanf("%d%d",&n,&m)) {
inc(i,,n) scanf("%s",G[i]+);
inc(i,,n+m) fa[i]=i;
inc(i,,n) inc(j,,m) // 第二行的编号为n+j
if(G[i][j]=='=') fa[getfa(i)]=getfa(n+j);
// 相等的连到同一个父亲
bool OK=; mem(E,); mem(du,);
inc(i,,n) inc(j,,m)
if(G[i][j]!='=') {
int fi=getfa(i), fj=getfa(n+j);
// 父亲相同说明相等 但此时是不等的情况 则无解
if(fi==fj) OK=;
else {
if(G[i][j]=='<'&&E[fi][fj]==)
E[fi][fj]=, du[fj]++;
else if(G[i][j]=='>'&&E[fj][fi]==)
E[fj][fi]=, du[fi]++;
} // 由小向大连边 并计算点的入度
}
if(OK==) { puts("No"); continue; }
queue<int>q;
inc(i,,n+m) // 入度为0说明是最小的
if(du[i]==) q.push(i), ans[i]=;
while(!q.empty()) {
int u=q.front(); q.pop();
inc(i,,n+m)
if(E[u][i] && --du[i]==) // 入度减1 即去掉u点
q.push(i), ans[i]=ans[u]+;
// 入度减为0说明没有比他更小的了
}
inc(i,,n+m) if(du[i]) OK=;
if(OK==) { puts("No"); continue; }
puts("Yes");
inc(i,,n) printf("%d ",ans[getfa(i)]); printf("\n");
inc(i,,m) printf("%d ",ans[getfa(n+i)]); printf("\n");
} return ;
}
05-13 05:58