- 读懂题后,发现就是个 (n=1000,m=n^2) 的差分约束,并要求输出各个权值最小的方案.一开始用 (spfa) 最长路做,但错了些小细节.改过来后发现 (T) 了.
- 为什么呢?因为 (spfa) 找环其实就是 (Bellman-Ford) ,时间复杂度为 (O(nm))...
- 由于这道题的约束形式只有 ({v_i-v_jgeq c}) , 可以保证连出的边权都为正.
- 用 缩点+拓扑排序 就可以了.先预处理出要求权值相同的点,用并查集缩成一个点.
- 然后再来连边,因为所有的边都是正权的,判是否有正权环等价于是否有环(否则还是要用 (spfa) 做),用拓扑排序 (O(n+m)) 判断.
- 若有解,说明图是一个 (DAG) ,在 (DAG) 上找从每个点出发的最长路长度,显然是 (O(n)) 的.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
inline int read()
{
int x=0;
bool pos=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
pos=0;
for(;isdigit(ch);ch=getchar())
x=x*10+ch-'0';
return pos?x:-x;
}
const int MAXN=2e3+100;
const int MAXM=1e6+2000;
int n,m;
int cnt,nx[MAXM],to[MAXM],head[MAXN];
int fa[MAXN],siz[MAXN];
int indeg[MAXN];
int valid;
int tot=0;
int Find(int x)
{
return fa[x]==x?x:fa[x]=Find(fa[x]);
}
void add(int u,int v)
{
++cnt;
nx[cnt]=head[u];
to[cnt]=v;
head[u]=cnt;
}
char buf[1010][1010];
int dis[MAXN];
bool vs[MAXN];
void Assign(int u)
{
dis[u]=1;
vs[u]=1;
for(int i=head[u];i;i=nx[i])
{
int v=to[i];
if(!vs[v])
Assign(v);
dis[u]=max(dis[u],dis[v]+1);
}
}
void pr_yes()
{
Assign(0);
puts("Yes");
for(int i=1;i<=n;++i)
{
printf("%d%c",dis[Find(i)],i==n?'
':' ');
}
for(int i=n+1;i<=n+m;++i)
{
printf("%d ",dis[Find(i)]);
}
puts("");
}
bool vis[MAXN];
void dfs(int u)
{
for(int i=head[u];i;i=nx[i])
{
int v=to[i];
if(indeg[v])
{
--indeg[v];
if(!indeg[v])
++tot,dfs(v);
}
}
}
int main()
{
n=read();
m=read();
for(int i=1;i<=m+n;++i)
dis[i]=-1e9,fa[i]=i,siz[i]=1;
valid=n+m;
for(int i=1;i<=n;++i)
{
scanf("%s",buf[i]+1);
for(int j=n+1;j<=n+m;++j)
{
int u=Find(i),v=Find(j);
if(buf[i][j-n]=='<')
{
continue;
}
else if(buf[i][j-n]=='>')
{
continue;
}
else
{
if(u!=v)
{
if(siz[u]<siz[v])
swap(u,v);
fa[v]=u;
siz[u]+=siz[v];
--valid;
}
}
}
}
for(int i=1;i<=n;++i)
{
for(int j=n+1;j<=n+m;++j)
{
int u=Find(i),v=Find(j);
if(buf[i][j-n]=='<')
{
add(v,u);
++indeg[u];
}
else if(buf[i][j-n]=='>')
{
add(u,v);
++indeg[v];
}
else
continue;
}
}
for(int i=1;i<=n+m;++i)
{
int u=Find(i);
if(!vis[u])
vis[u]=1,add(0,u),indeg[u]++;
}
dfs(0);
if(tot<valid)
return puts("No")&0;
pr_yes();
return 0;
}