hdu 2647 Reward(拓扑排序+反图)

题目链接：https://vjudge.net/contest/218427#problem/C

题目大意：

老板要给很多员工发奖金， 但是部分员工有个虚伪心态， 认为自己的奖金必须比某些人高才心理平衡； 但是老板很人道， 想满足所有人的要求， 并且很吝啬，想画的钱最少

输入若干个关系

a b

a c

c b

意味着a 的工资必须比b的工资高 同时a 的工资比c高； c的工资比b高

当出现环的时候输出-1。所有人的工资都不能少于888.

#include <bits/stdc++.h>
using namespace std;

#define REP(i,s,t) for(int i=s;i<=t;i++)
const int N = 1e4+5;
vector<int>G[N];
int n,m,sum;
int in[N],mon[N];
void topusort(){
    queue<int>q;
    for(int i=1;i<=n;i++) if(!in[i])q.push(i);
    int ans=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        sum+=mon[u];
        ans++;
        for(auto v:G[u]){
            if(--in[v]==0){
                q.push(v);
                mon[v]=mon[u]+1;    
            }
        }
    }
    if(ans!=n)sum=-1;          //如果有环的话
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        sum=0;
        memset(in,0,sizeof(in));
        for(int i=0;i<=n;i++)G[i].clear(),mon[i]=888;
        REP(i,1,m){
            int u,v;scanf("%d%d",&u,&v);
            G[v].push_back(u);           //建反图
            in[u]++;
        }
        topusort();
        cout<<sum<<endl;
    }
}

2018-04-10