[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;
}