Acwing 1192. 奖金(拓扑排序+排序中的同等地位判断)

地址：https://www.acwing.com/problem/content/1194/

 

解析：

一：刚开始以为直接拓扑排序，然后累加奖金即可，每次奖金++

但这样是不对的。

给出样例：

3 2

1 2

1 3

2和3其实在图中处于同等地位，它俩的奖金应该一样， 答案是101+100+100==301。而不是302

所以并不能简单地累加

二：判断同等地位

加入w[]数组记录每个人的奖金

回顾一下拓扑排序的删边过程，如果对于一个点，遍历它的出边一个for，能使得多个点入度变为0，那么这些个点，就处于同等地位。

所以初始把入度为0的点奖金定位100，往后的过程中，如果某个点入度减为0，那么其奖金就是它的父节点奖金+1

#include<iostream>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<queue>
using namespace std;
const int maxn=3e4+10;
int ans[maxn],tot=0;
int e[maxn],ne[maxn],idx,h[maxn],d[maxn],w[maxn];
int n,m,sum=0;
bitset<maxn>f[maxn];
void init()
{
    memset(h,-1,sizeof(h));
    idx=0;
}
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void bfs()
{
    queue<int>q;
    for(int i=1;i<=n;i++)
        if(d[i]==0)
        {
            q.push(i);
            w[i]=100;    
        }
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        ans[tot++]=t;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(d[j]==0)
            {
                q.push(j);
                w[j]=w[t]+1;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    init();
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(b,a);//利于w[]的计算，所以换一下
        d[a]++;
    }
    bfs();
    if(tot<n)
        cout<<"Poor Xed"<<endl;
    else
    {
        for(int i=1;i<=n;i++)
        {
            //cout<<w[i]<<" ";
            sum+=w[i];
        }
        cout<<sum<<endl;
    }
}