AcWing 1192. 奖金
原题链接
简单
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=2e4+10;
int n,m;
int h[N],ne[M],e[M],idx;
int w[N];
int q[N],ind[N],hh=0,tt=-1;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void topsort()
{
for(int i=1; i<=n; i++)
if(!ind[i]) w[i]=100,q[++tt]=i;//入度為0代表沒有人的獎金比他少
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t]; ~i; i=ne[i])
{
int j=e[i];
if(--ind[j]==0)
{
w[j]=w[t]+1;
q[++tt]=j;
}
}
}
}
int main()
{
memset(h,-1,sizeof h);
cin>>n>>m;
while(m--)
{
int a,b;
cin>>a>>b;
add(b,a);//建反向邊,因為要從最小的開始
ind[a]++;
}
topsort();
int res=0;
for(int i=1; i<=n; i++)
{
if(w[i]==0)
{
cout<<"Poor Xed";
return 0;
}
res+=w[i];
}
cout<<res;
return 0;
}