Codeforces Round #541 (Div. 2)：Gourmet choice【拓扑排序】

75 阅读 0 评论 50 点赞

我是靠谱客的博主饱满音响，最近开发中收集的这篇文章主要介绍Codeforces Round #541 (Div. 2)：Gourmet choice【拓扑排序】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

给你n个美食和另外m个美食的评分的大小关系，求出每个美食的评分，并满足最高的分最低

分析：

容易想到拓扑排序，对于相等的点用并查集缩成一个点，对于不一样大的点建一条有向边（小->大），建边时要判断两点是否相等（有无矛盾的关系），如果有向图存在环也是不符合题意的，可以在最后判断n+m个点是否都有大于零的值

代码：

#include <bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int MAXN = 1e6+16;
int n,m,pre[MAXN],cnt,in[MAXN],val[MAXN],head[MAXN];
char s[1010][1010];
struct edge{
    int v,nxt;
}e[MAXN];
void init()
{
    for(int i = 0;i <= n+m; ++i) pre[i] = i;
}
void add(int u,int v)
{
    e[++cnt].v = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
    in[v]++;
}
int Find(int x)
{
    int t = x;
    while(t != pre[t]) t = pre[t];
    while(x != pre[x])
    {
        int tep = pre[x];
        pre[x] = t;
        x = tep;
    }
    return t;
}
void mix(int x,int y)
{
    int fx = Find(x);
    int fy = Find(y);
    if(fx != fy) pre[fx] = fy;
}
void solve()
{
     queue<pii> p;
     for(int i = 1;i <= n+m; ++i){
        if(!in[i]) p.push(pii(i,1));
     }
     while(!p.empty())
     {
        pii w = p.front();p.pop();
        val[w.f] = w.s;
        for(int i = head[w.f]; i ; i = e[i].nxt){
            if(--in[e[i].v] == 0) p.push(pii(e[i].v,w.s+1));
        }
     }
     for(int i = 1;i <= n+m; ++i){
        val[i] = val[Find(i)];
        if(!val[i]){
            cout<<"No";
            return ;
        }
     }
     cout<<"Yes"<<endl;
     for(int i = 1;i <= n; ++i) cout<<val[i]<<" ";
     cout<<'n';
     for(int i = n+1; i <= n+m; ++i) cout<<val[i]<<" ";
}
int main()
{
    cin>>n>>m;
    init();
    for(int i = 1;i <= n; ++i) scanf("%s",s[i]+1);
    for(int i = 1;i <= n; ++i){
        for(int j = 1;j <= m; ++j){
            if(s[i][j] == '=') mix(i,n+j);
        }
    }
    bool vis = true;
    for(int i = 1;i <= n; ++i){
        for(int j = 1;j <= m; ++j){
            if(s[i][j] == '<'){
                if(Find(i) != Find(n+j)) add(Find(i),Find(n+j));
                else vis = false;
            }
            else if(s[i][j] == '>'){
                if(Find(i) != Find(n+j)) add(Find(n+j),Find(i));
                else vis = false;
            }
        }
    }
    if(!vis) cout<<"No";
    else solve();
    return 0;
}