原题链接:D. Gourmet choice
题目大意
给出一个(n*m)的二维字符数组,其中(s_{i,j})表示(a_i)与(b_j)的关系,如相等,小于或大于.求是否存在一组({a},{b})使得能满足条件,如果能则输出最大值最小的解,如果不能输出无解.
数据范围:
(1 leq n,m leq 1000)
思路
显然所有相等的元素,可以先合并到一起,这一步可以并查集来做,不过需要拓展域:([1,n])的元素,维护的是(a_i)属于哪个集合,([n+1,m])的元素维护的是(b_j)属于哪个集合.合并完之后考虑小于和大于的偏序关系,很显然是让相同的元素的集合看做是一整个块再去和别的集合连边,那么为了保证最大值最小,如果关系是(a_i<b_j)那么就让(a_i)所在的集合连一条有向边到(b_j)所在的集合,那么如果(a_i)和(b_j)本来就是一个集合的,这里又出现了一个偏序关系,则显然是无解的.连完边之后,整个图应该是一个有向图,而且一旦存在环就意味着产生了一个形如(a_i>b_j>...>a_i)的结构,显然也是无解的.那么把出现有环的情况再删除之后,整个图就是一个有向无环图了,对之直接拓扑排序即可.
检查是否存在环这一步也应该放在拓扑排序里,简单的搜索被挂了一个TLE.
其次,拓扑排序的点是并查集合并之后的"代表元素",那么就不能用原有给定的下标了,所以代码实现的时候先把所有的入度初始化成-1,而只有当某个代表元素,也就是新的图上的点的编号被拿出来的时候才会给这个(deg[i])赋值成(0).之后拓扑排序判环的时候也不能判断出队的元素是否是(n+m)个而是新的点数.
当然,这个题还有个坑点,假如说有解的话,所有的答案最小值都是(1),如果不对所有(ans)一开始就赋值的话,而是等到在拓扑排序的时候再对入度为(0)的点进行赋值为(1)的操作,那么假如整个图上就没有任何的偏序关系,他也是可能有解的,但是此时的答案就会输出成(0)而正确答案是(1),因为此时拓扑排序都没启动,没有正确的对所有起点赋初值.当然解决办法就是一开始就直接对所有点赋初值.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
const int N = 1005;
char s[N][N];
int fa[2 * N],st[N * 2],ans[N * 2],deg[N * 2];
int n,m,in_path[N * 2];
vector<int> E[N * 2];
int find(int x)
{
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int topo()
{
queue<int> q;
forn(i,1,n + m) if(deg[i] == 0) q.push(i);
int in_times = 0;
while(!q.empty())
{
++in_times;
int u = q.front();q.pop();
for(auto& v : E[u])
{
if(--deg[v] == 0)
q.push(v),ans[v] = ans[u] + 1;
}
}
return in_times;
}
int main()
{
scanf("%d%d",&n,&m);
forn(i,1,n) scanf("%s",s[i] + 1);
forn(i,1,n + m) fa[i] = i,ans[i] = 1;
forn(i,1,n) forn(j,1,m)
if(s[i][j] == '=')
{
int x = find(i),y = find(j + n);
if(x == y) continue;
fa[x] = y;
}
memset(deg,-1,sizeof deg);
int fuck = 0;
forn(i,1,n) forn(j,1,m)
{
if(s[i][j] == '=') continue;
int x = find(i),y = find(j + n);
if(deg[x] == -1) deg[x] = 0,++fuck;
if(deg[y] == -1) deg[y] = 0,++fuck;
if(x == y) return puts("No"),0;
if(s[i][j] == '<') E[x].push_back(y),++deg[y];
else E[y].push_back(x),++deg[x];
}
if(topo() != fuck) return puts("No"),0;
puts("Yes");
forn(i,1,n) printf("%d ",ans[find(i)]);puts("");
forn(i,1,m) printf("%d ",ans[find(i + n)]);
return 0;
}