【upc】奶茶 (milktea)

奶茶 (milktea)"/>

【upc】奶茶 (milktea)

问题 F: 奶茶 (milktea)

时间限制: 2 Sec  内存限制: 128 MB
提交 状态

题目描述

光阴荏苒，飞鱼奶茶店已经开业几个月了。这天，老翁到奶茶店里买奶茶，顺便问了小鱼一个问题。

老翁原先有n+m个正整数，分别是a1,a2,...,an,b1,b2,...,bn，但它们被小Y吃了。她忘记了这些数具体是多少，只记得对于每个数对(i,j)，ai和bj的大小关系（可能是大于，小于或者等于）。她还记得这些正整数的中最小的恰为1。

老翁问小鱼，在已知条件下，这n+m个正整数中每个数的最小值分别是多少。若不存在这样的a1,a2,...,an,b1,b2,...,bn，那一定是老翁记错了，这时你需要输出No。

小鱼当然不屑于算这种问题。于是他希望你写程序来解决。

输入

输入的第一行是一个正整数T，表示这个测试点有T组数据。

对于每组数据：

第一行两个正整数n,m。

接下来的n行，每行是一个由m个字符构成的字符串。其中的第i行第j列描述的是ai和bj的大小关系。具体地：
·第i行第j列为=表示ai=bj；
·第i行第j列为<表示ai<bj；
·第i行第j列为>表示ai>bj。

输出

对于每组数据：

若存在答案，输出三行：

第一行是一个Yes；

第二行n个正整数，其中第i个表示ai的最小值；

第三行m个正整数，其中第j个表示bj的最小值。

若不存在答案，输出一行一个No，接下来你不需要也不应该输出两个空行。

样例输入 Copy

3
3 4
>>>>
>>>>
>>>>
3 2
==
=<
==
3 3
>>>
<<<
>>>

样例输出 Copy

Yes
2 2 2
1 1 1 1
No
Yes
3 1 3
2 2 2

题目大意：

中文题意

题目思路：

考虑如果没有 = 的话 就可以直接建图

之后利用拓扑排序的性质去跑一下dp

有了 = 怎么办呢？

一样，把相同的点 利用并查集缩点不就好啦

Code:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int Maxn=1e6+10;
const int maxn =1e6+10;
const int mod= 1e9+7;
const int Mod = 1e6+7;
///const double eps=1e-10;
inline bool read(ll &num)
{char in;bool IsN=false;in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
char mp[2005][2005];
int pre[maxn],in[maxn],dp[maxn];
vector<int>v[maxn];
int Find(int x){return pre[x] == x?x:pre[x] = Find(pre[x]);
}
queue<int>q;
int main()
{int T;scanf("%d",&T);while(T--){read(n);read(m);for(int i=1;i<=n+m;i++) pre[i] = i,in[i] = 0,dp[i] = 0,v[i].clear();for(int i=1;i<=n;i++)scanf("%s",mp[i]+1);for(int i=1;i<=n;i++){for(int k=1;k<=m;k++){if(mp[i][k] == '='){int dx = Find(i),dy = Find(n+k);if(dx != dy) pre[dx] = dy;}}}for(int i=1;i<=n;i++){for(int k=1;k<=m;k++){if(mp[i][k] == '=') continue;int dx = Find(i),dy = Find(n+k);if(mp[i][k] == '>'){///a[i] > b[k]in[dx]++;v[dy].push_back(dx);}else{in[dy]++;v[dx].push_back(dy);}}}while(!q.empty()) q.pop();for(int i=1;i<=n+m;i++)if(!in[i]){q.push(i);dp[i] = 1;}int cnt = 0;while(!q.empty()){int u = q.front();q.pop();cnt++;for(int e:v[u]){in[e]--;dp[e] = max(dp[e],dp[u]+1);if(!in[e]) q.push(e);}}if(cnt<n+m) printf("No\n");else{printf("Yes\n");for(int i=1;i<=n;i++) printf("%d ",dp[Find(i)]);printf("\n");for(int i=n+1;i<=n+m;i++) printf("%d ",dp[Find(i)]);printf("\n");}}return 0;
}