[cf541D]Gourmet choice (缩点+dfs)

Gourmet choice

题意

给定$n$个蛋糕和$m$个蛋糕,和他们之间的大小关系。问给所有的蛋糕一个可能最小的值,使得关系成立。

题解

首先由于有$=$的存在,有一些蛋糕的值是要一样的。所以我们需要把题目中的相等的点给缩到一起。

之后用dfs把值给确定下来。

其中缩点用到的技巧很厉害。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 2e3+10;
vector<int> e[maxn];
// m is behind of the n
int fa[maxn];
int Find(int x){
return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
void Union(int i,int j){
int x = Find(i);
int y = Find(j);
if(x!=y) fa[x] = y;
}
int ind[maxn],use[maxn],vis[maxn];
char mx[maxn][maxn];
int n,m;
// flag means the 矛盾
bool flag;
int dp[maxn];
void dfs(int x,int dep){
if(flag) return ;
dp[x] = max(dp[x],dep);
for(auto to:e[x]){
if(vis[to]) {
flag = true;
return ;
}
if(dep+1>dp[to]){
vis[to] = 1;
dfs(to,dep+1);
vis[to] = 0;
}
}
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
rep(i,0,n){
scanf("%s",mx+i);
}
rep(i,0,n+m) fa[i] = i;
rep(i,0,n)
rep(j,0,m)
if(mx[i][j] == '=')
Union(i,n+j);
rep(i,0,n) rep(j,0,m){
int x = Find(i); int y = Find(j+n);
if(mx[i][j] == '<'){
e[x].push_back(y);
ind[y] ++;
use[x] = 1;
}else if(mx[i][j] == '>'){
e[y].push_back(x);
ind[x] ++;
use[y] = 1;
}else{
use[x] = 1;
}
}
bool fflag = false;
rep(i,0,n+m){
if(use[i] && ind[i] == 0){
fflag = true;
vis[i] = 1;
dfs(i,1);
vis[i] = 0;
}
}
if(fflag == false || flag){
puts("No");
}else{
puts("Yes");
rep(i,0,n) printf("%d ",dp[Find(i)]);
puts("");
rep(i,n,m+n) printf("%d ",dp[Find(i)]);
}
return 0;
}