Reward（拓扑排序）

╰+哭是因爲堅強的太久メ 2022-08-02 01:30 8阅读 0赞

![20150705172048416][]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<vector>
    #include<queue>
    /*
    这一题很好，用到了拓扑排序（从后往前），由于这一题数据比较大所以用vector来存储！
    存储过程中会出现这一个问题！ 
    4 3
    1 2
    2 3
    1 4
    这样的一个问题怎么解决呢？
    3->2>1
    4->1这个问题4和3是888，2是889，那么1是多少合适呢？
    是889（大于4）还是890（大于1）呢？由题意我们知道是890
    用程序怎么判断呢？
    程序是通过队列来实现的
    你比如这个点
    压进去3 4
    弹出3 压进去 2此时队列里有4 2
    弹出4 更新1的值为899 压进1
    弹出2 更新一的值为890
    弹出1
    通过队列的长度来决定更新前面一个值得先后顺序！
    还可以通过队列来判断是否有环，出栈之后栈是否为空！
    */
    const int maxs=10010;
    using namespace std;
    vector<int>vec[maxs];
    int indegree[maxs],money[maxs];
    int n,m;
    int toposort()
    {
        int i,j,k,num,tmp;
        num=n;
        queue<int>q;
        for(i=1;i<=n;i++)
        {
            if(indegree[i]==0)
            {
                q.push(i);//压进去！
            }
        }
        while(!q.empty())
        {
            num--;//最后判断num是否为0，判断是否有圈！
            j=q.front();
            tmp=money[j];//获取此时j的工资！
            q.pop();//弹出！
            for(k=0;k<vec[j].size();k++)
            {
                indegree[vec[j][k]]--;
                if(indegree[vec[j][k]]==0)
                {
                    money[vec[j][k]]=tmp+1;
                    q.push(vec[j][k]);
                }
            }
        }
        if(num>0)
        {
            return 0;
        }
        else
        {
            return 1;
        }
    }
    int main()
    {
        int i,a,b,sum;
        while(cin>>n>>m)
        {
            sum=0;
            for(i=0;i<=n;i++)
            {
                money[i]=indegree[i]=0;
                vec[i].clear();
            }
            for(i=1;i<=m;i++)
            {
                cin>>a>>b;
                vec[b].push_back(a);
                indegree[a]++;//a的入度加一！
            }
            if(toposort())
            {
                for(i=1;i<=n;i++)
                {
                    sum+=money[i];
                }
                cout<<sum+888*n<<endl;
            }
            else
            {
                cout<<-1<<endl;
            }
        }
    }

[20150705172048416]: /images/20220731/06f24eea7e894728947877a4f47bb192.png