问题 1: 奖金

时间限制: 1 Sec  内存限制: 600 MB
提交: 22  解决: 8
[提交][状态][讨论版][命题人:quanxing]

题目描述

【问题描述】

由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。

【输入格式】

第一行两个整数n,m，表示员工总数和代表数；以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。

【输出格式】

若无法找到合理方案，则输出“Poor Xed”；否则输出一个数表示最少总奖金。

【输入样例】

2 1

1 2

【输出样例】

201

样例输入

2 1
1 2

样例输出

201

 

 

 
#include<cstdio>
#include<cmath> 
#include<iostream> 
#include<cstring> 
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<iomanip>
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
const int maxn=30000;
int n,m,a,b,in[maxn*2],f[maxn]={0},sum=0;
//in数组为入度，用于判断是否是链的起始点
//f数组用于记录各个点在各条链上的最大位置
vector<int> G[maxn];
queue<int> qe;
int topo(){
    int cnt=0;        //记录图中用了几个点 
    for(int i=1;i<=n;i++)//起始点入队列 
        if(in[i]==0)    qe.push(i); 
    while(!qe.empty()){
        int u=qe.front();
        qe.pop();
        cnt++;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];        //u指向v，u更小 
            f[v]=max(f[v],f[u]+1);     
            //dp写在层次往下的时候，更新v的最大位置 
            if(--in[v]==0)    qe.push(v);
        }
    }
    return cnt==n;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        G[b].push_back(a);
        in[a]++;
    }
    if(!topo())        //判断是否成环，成环不成立 
        printf("Poor Xed");
    else{
        for(int i=1;i<=n;i++)
            sum+=f[i];        
            //将各个点在各条链上的最大位置相加 
        printf("%d",100*n+sum);
    }
    return 0;
}

 

 

版权声明：本文为PdrEam原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/PdrEam/p/12526847.html