奖金(拓补排序的应用)

谁应该高谁的入度++,并记录下谁比低的高(低的得出度),所以入度为零的就是最低的(好不公平),找出所有最低的,将他们算作一层,奖金++(算是拓补排序吧)

#include<cstdio>
#include<cstring> 
#include<cmath>
using namespace std;
int n;
int r[9999];
int f[99][99];
int flag[999];
int m; 
int a[99999];
int c[9999][999];
int main()
{
    //freopen("reward.in","r",stdin); 
    //freopen("reward.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        c[b][++c[b][0]]=a;
        r[a]++;
    }
    int nn=n;
    int p=100;
    int sum=0;
    for(;nn>=1;)
    {
        int x=1;
        int t=0;
        while(x<=n)
        {
        if(r[x]==0) 
        {
        sum+=p,r[x]=999999999,nn--,a[++t]=x;    
        }
        x++;
        }   
        if(t==0) 
        {
        printf("Poor Xed"); 
        return 0;
        }
        for(int j=1;j<=t;j++)
        for(int i=1;i<=c[a[j]][0];i++)
        {
            r[c[a[j]][i]]--;
        }
        p++;

    }
    printf("%d",sum);
    //fclose(stdin);
    //fclose(stdout); 
    return 0;
} 
原文地址:https://www.cnblogs.com/wspl98765/p/6819892.html