题解 CF1131D 【Gourmet choice】

题解-CF1131D Gourmet choice

• 题目意思

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

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

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

• 若为则：从并且统计的度加加
• 若为则：从并且统计的度加加

这样做完一遍我们就形成了一个。于是只要在这张图上跑一下拓扑就可以了，在途中用表示答案，因为题目要求求最大值最小，所以

• 

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