题意：有两组食物，分别有$n$个和$m$个。
给定$n\times m$的一个表格，其中$a[i][j]$表示第一组第$i$个食物和第二组第$j$个食物的美味度大小关系。
请问是否能给出一组美味度方案。如果有，请给出美味度最大值最小的方案。如果没有，请输出No.
先膜LCJ
本题如果数据出小一点就是差分约束系统的裸题。
但是到了现在的数据大小，差分约束无法承受，所以考虑用并查集+拓扑排序解决。
把=的食物用并查集并起来。然后对于>和<的情况，如果这俩元素在一个联通块里，显然不能构造。
否则，如果$a[i][j]= ‘<’$就从$i$的连通块向$j$连一条边，反之亦然。
然后对联通块跑拓扑排序即可。注意有环也不能构造。
正确性很显然：对于$v$，如果被删成了入度$=0$，那么上一次它只需要满足$u$的限制即可。
故$value[v] = value[u] + 1$.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109/**
* @Author: Mingyu Li
* @Date: 2019-03-09T22:42:11+08:00
* @Email: class11limingyu@126.com
* @Filename: c1131D.cpp
* @Last modified by: Mingyu Li
* @Last modified time: 2019-03-10T06:53:10+08:00
*/
#include <bits/stdc++.h>
#define tpname typename
#define Go(i , x , y) for(register int i = x; i <= y; i++)
#define God(i , y , x) for(register int i = y; i >= x; i--)
typedef long long LL;
typedef long double ld;
typedef unsigned long long ULL;
template < tpname T > void sc(T& t) {
char c = getchar(); T x = 1; t = 0; while(!isdigit(c)) {if(c == '-') x = -1; c = getchar();}
while(isdigit(c)) t = t * 10 + c - '0' , c = getchar();t *= x;
}
template < tpname T , tpname... Args > void sc(T& t , Args&... args) {sc(t); sc(args...);}
template < tpname T > T mul(T x , T y , T _) {
x %= _,y %= _; return ((x * y - (T)(((ld)x * y + 0.5) / _) * _) % _ + _) % _;
}
const int N = 1000 + 5;
int f[N + N];
int find(int x) {
return x == f[x] ? f[x] : f[x] = find(f[x]);
}
std::vector <int> v[N + N] , Graph[N + N];
std::map <std::pair<int,int>,int> alr;
char a[N][N];
int n , m;
int merge(int u , int v) {
f[find(u)] = find(v);
}
int rf;
int degree[N + N] , ans[N + N];
void Link(int u , int v) {
if(u == v) {
rf = 1;
return ;
}
if(alr[{u , v}]) return ;
alr[{u , v}] = 1;
Graph[u].push_back(v);
++degree[v];
}
int main() {
sc(n , m);
Go(i , 1 , n)
scanf("%s" , (a[i] + 1));
Go(i , 1 , n+m) f[i] = i;
Go(i , 1 , n) Go(j , 1 , m) if(a[i][j] == '=') merge(i , n+j);
std::vector <int> v1;
Go(i , 1 , n+m) v[find(i)].push_back(i) , v1.push_back(find(i));
Go(i , 1 , n)
Go(j , 1 , m) {
if(a[i][j] == '<') Link(find(i) , find(n+j));
else if(a[i][j] == '>') Link(find(n+j) , find(i));
}
if(rf) {
puts("No");
return 0;
}
std::queue <std::pair <int , int> > Q;
sort(v1.begin() , v1.end());
int m1 = unique(v1.begin() , v1.end()) - v1.begin();
std::vector <int> v2;
Go(i , 0 , m1-1) if(!degree[v1[i]]) {
Q.push({v1[i] , 1}); v2.push_back(v1[i]);
for(auto fix : v[v1[i]]) ans[fix] = 1;
}
while(!Q.empty()) {
std::pair < int , int > x = Q.front(); Q.pop();
int u = x.first , va = x.second;
for(auto vv : Graph[u]) {
degree[vv]--;
if(!degree[vv]) {
degree[vv] = 0;
Q.push({vv , va + 1});
v2.push_back(vv);
}
}
}
Go(i , 0 , v2.size() - 1) {
for(auto fix : v[v2[i]]) ans[fix] = i + 1;
}
int ans1 = 0;
Go(i , 1 , n+m) ans1 += (degree[find(i)] == 0);
//std::cerr << "\n";
if(ans1 != n+m) {
puts("No");
return 0;
}
std::cout << "Yes\n";
Go(i , 1 , n) std::cout << ans[i] << " ";
std::cout << "\n";
Go(i , 1 , m) std::cout << ans[n + i] << " ";
std::cout << "\n";
return 0;
}