「Codeforces 1131D」Gourmet Choice

发表于 | | 阅读次数:
字数统计: 774 字

Description

题目链接：Codeforces 1131D

美食家 Apple 先生是一家美食杂志的主编。他会用一个正整数来评价每一道菜。

美食家在第一天品尝第 $n$ 道菜，第二天品尝了 $m$ 道菜。他制作了一张 $n\times m$ 的表格，记录了他对菜肴的评价。如果第一套中的第 $i$ 道菜比第二套中的第 $j$ 道菜好，那么 $a_{i,j}$ 等于 >；如果要差，那么 $a_{i,j}$ 等于 <。菜肴可能同样美味，那么 $a_{i,j}$ 等于 =。

现在 Apple 先生想让你帮他评价每道菜。由于他是非常严格的，他会对菜肴进行评估，以便使用的最大整数尽可能小。但是 Apple 先生也很公平，如果 $a_{i,j}$ 为 <，那么给第一套中第 $i$ 道菜的评价一定小于第二套中第 $j$ 道菜。如果 $a_{i,j}$ 是 > 那么应该要更大。如果 $a_{i,j}​$ 为 =，那么这两个数字要相等。

帮助 Apple 先生评价这两套中的每一道菜，使之符合他的感受，并满足最大数字尽可能小。如果有解则输出 Yes 和评价的数字；否则输出 No。

数据范围：$1\le n,m\le 10^3$。

Solution

首先我们把 = 给处理掉，把所有相等的点缩在一起。如果同一个并查集中的点有 < 或 > 关系显然无解。

此时我们得到了一个有向图，直接对它拓扑排序，如果有环则无解，否则输出方案。

时间复杂度：$O(nm)$

Code

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
 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define fail puts("No"),exit(0)

const int N=2e3+5,M=2e6+5;
int n,m,cnt,tot,lnk[N],ter[M],nxt[M],fa[N],bel[N],deg[N],dis[N];
bool vis[N];
char s[N][N];

void add(int u,int v) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,++deg[v];
}
int find(int x) {
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void init() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+m;++i) fa[i]=i;
    for(int i=1;i<=n;++i) {
        scanf("%s",s[i]+1);
        for(int j=1;j<=m;++j) if(s[i][j]=='=') fa[find(i)]=find(n+j);
    }
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
        if(s[i][j]!='='&&find(i)==find(n+j)) fail;
    }
    for(int i=1;i<=n+m;++i) if(find(i)==i) bel[i]=++cnt;
    for(int i=1;i<=n+m;++i) bel[i]=bel[find(i)];
}
void build() {
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
        if(s[i][j]=='<') add(bel[i],bel[j+n]);
        if(s[i][j]=='>') add(bel[j+n],bel[i]);
    }
}
void solve() {
    std::queue<int> q;
    for(int i=1;i<=cnt;++i) if(!deg[i]) dis[i]=1,q.push(i);
    while(!q.empty()) {
        int u=q.front(); q.pop();
        vis[u]=1;
        for(int i=lnk[u];i;i=nxt[i]) {
            int v=ter[i];
            dis[v]=std::max(dis[v],dis[u]+1);
            if(!--deg[v]) q.push(v);
        }
    }
    for(int i=1;i<=cnt;++i) if(!vis[i]) fail;
    puts("Yes");
    for(int i=1;i<=n+m;++i) {
        printf("%d%c",dis[bel[i]]," \n"[i==n||i==n+m]);
    }
}
int main() {
    init();
    build();
    solve();
    return 0;
}
0%