T22508: 最小奖金方案

topologic sort, http://cs101.openjudge.cn/practice/22508/

【姚博骞 25物院】思路：构建图，记录出度和入度的来源数组，这个学期也可以学习一下基本图论，以前没怎么搞过数学竞赛。 关键的转移方程： prize[beatenby[i][j]]=max(prize[beatenby[i][j]],prize[i]+1);

#include<iostream>
#include<queue>
#include<vector>
#include<unordered_map>
using namespace std;
int max(int a,int b)
{
    return (a>b)?a:b;
}
int main()
{
    //记录每个队伍打败的队伍数量，以及被打败的队伍的集合
    //考虑拓扑排序，肯定要一个也没打败的，直接把打败他的队伍奖金都变成max（now，ta+1），然后踢出去。
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>>pk;
    vector<int> prize(n,100);
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        pk.push_back({a,b});
    }
    //构建图
    vector<int>num_beat(n,0);
    vector<vector<int>>beatenby(n,vector<int>(0));
    for(int i=0;i<m;i++)
    {
        num_beat[pk[i].first]++;
        beatenby[pk[i].second].push_back(pk[i].first);
    }
    queue<int>q;
    for(int i=0;i<n;i++)
    {
        if(!num_beat[i]) q.push(i);
    }
    while(!q.empty())
    {
        int i=q.front();
        q.pop();
        for(int j=0;j<beatenby[i].size();j++)
        {
            num_beat[beatenby[i][j]]--;
            prize[beatenby[i][j]]=max(prize[beatenby[i][j]],prize[i]+1);
            if(num_beat[beatenby[i][j]]==0) q.push(beatenby[i][j]);
        }
    }
    int ans=0;
    for(int i=0;i<n;i++)
    {
        ans+=prize[i];
    }
    cout<<ans;
    return 0;
}