题解 CF1131D 【Gourmet choice】

题解-CF1131D Gourmet choice

题目意思

就是给你很多个约束条件,让你求出合法的序列 $a,b$ 满足条件且最大值最小的方案。

$Solution$

$tarjan+topu$

对于一开始的那些 $=$ 条件我们先让 $i$ 以及 $j+n$ 放入同一个连通块里。
第二次再做一遍，如果两个处于同一个联通块的点又有 $> or <$ 的关系显然就只要输出 $No$ 即可。

然后第二次做关于大于小于关系的点的时候：

若为 $<$ 则：从 $jia(i,j+n)$ 并且统计 $j+n$ 的度加加
若为 $>$ 则：从 $jia(j+n,i)$ 并且统计 $i$ 的度加加

这样做完一遍我们就形成了一个 $DAG$ 。于是只要在这张图上跑一下拓扑就可以了，在途中用 $f[]$ 表示答案，因为题目要求求最大值最小，所以 $f[v]=\max(f[v],f[u]+1)$

$Code$

#include <bits/stdc++.h>
using namespace std;

const int maxn=2005;
const int maxm=maxn*maxn;

int n,m,cnt,ans,top,sum,tot,now;
int head[maxm],col[maxm],stak[maxm];
int low[maxm],dfn[maxm],gs;
int f[maxm],du[maxm],vis[maxm];
char c[maxn][maxn];

struct nood {
    int nex,to;
};
nood e[maxm<<2];//n*m的边

inline void jia(int u,int v) {
    e[++cnt].nex=head[u];
    head[u]=cnt;
    e[cnt].to=v;
}

inline void tarjan(int u) {
    low[u]=dfn[u]=++now;
    stak[++top]=u;
    for ( int i=head[u];i;i=e[i].nex ) {
        int v=e[i].to;
        if(!dfn[v]) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else 
            if(!col[v]) 
                low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]) {
        col[u]=++sum;
        while(u!=stak[top]) {
            col[stak[top]]=sum;
            top--;
        }
        top--;
    }
}

inline int read() {
    int sum=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) 
        sum=sum*10+(ch^48),ch=getchar();
    return sum;
}

inline void write(int x) {
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(x>9) 
        write(x/10);
    putchar(x%10+48);
}

inline void write_c(int x) {
    write(x);
    putchar(' ');
}

inline int max(int a,int b) {
    if(a>b) return a;
    return b;
}

int main() {
//    freopen("da.in","r",stdin);
//    freopen("da.out","w",stdout); 
    n=read();
    m=read();
    for ( int i=1;i<=n;i++ ) scanf("%s",c[i]+1);
    for ( int i=1;i<=n;i++ ) 
        for ( int j=1;j<=m;j++ ) 
            if(c[i][j]=='=') {
                jia(i,j+n); 
                jia(j+n,i);
            }
    for ( int i=1;i<=n+m;i++ ) 
        if(!dfn[i]) tarjan(i);
    memset(head,0,sizeof(head));
    cnt=0;
    for ( int i=1;i<=n;i++ ) 
        for ( int j=1;j<=m;j++ ) {
            if(c[i][j]=='>') {
                if(col[i]==col[j+n]) 
                    return printf("No\n"),0;
                jia(col[j+n],col[i]);
                ++du[col[i]];
            }
            if(c[i][j]=='<') {
                if(col[i]==col[j+n]) 
                    return printf("No\n"),0;
                jia(col[i],col[j+n]);
                ++du[col[j+n]];
            }
        }
    std::queue<int>q;
    for ( int i=1;i<=sum;i++ ) 
        if(!du[i]) {
            f[i]=1;
            q.push(i);
        }
//    for ( int i=1;i<=sum;i++ ) cout<<du[i]<<" "; cout<<endl;
//    for ( int i=1;i<=n+m;i++ ) cout<<col[i]<<" "; 
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        ++gs;
        for ( int i=head[u];i;i=e[i].nex ) {
            int v=e[i].to;
            --du[v];
            f[v]=max(f[v],f[u]+1);
            if(!du[v]) q.push(v);
        }
    }
//    for ( int i=1;i<=sum;i++ ) cout<<f[i]<<" "; 
    if(gs!=sum) 
        return printf("No\n"),0;
    putchar('Y');
    putchar('e');
    putchar('s');
    putchar('\n');
    for ( int i=1;i<=n;i++ ) write_c(f[col[i]]);
    printf("\n");
    for ( int i=1;i<=m;i++ ) write_c(f[col[i+n]]);
    return 0;
}