1192啥意思_拓扑排序怎么排

1192啥意思_拓扑排序怎么排由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出,Yali Company总经理Mr.Z心情好,决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是Mr.Z下令召开 m 方会谈。每位参加会谈的代表提出了自己的意见:“我认为员工 a 的奖金应该比 b 高!”Mr.Z决定要找出一种奖金方案,满足各位代表的意见,且同时使得总奖金数最少。每位员工奖金最少为100元,且必须是整数。输入格式第一行包含整数 n,m,分别表示公司内员工数以及参会代表数。接下来 m

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出,Yali Company总经理Mr.Z心情好,决定给每位员工发奖金。

公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。

于是Mr.Z下令召开 m 方会谈。

每位参加会谈的代表提出了自己的意见:“我认为员工 a 的奖金应该比 b 高!”

Mr.Z决定要找出一种奖金方案,满足各位代表的意见,且同时使得总奖金数最少。

每位员工奖金最少为100元,且必须是整数。

输入格式
第一行包含整数 n,m,分别表示公司内员工数以及参会代表数。

接下来 m 行,每行 2 个整数 a,b,表示某个代表认为第 a 号员工奖金应该比第 b 号员工高。

输出格式
若无法找到合理方案,则输出“Poor Xed”;

否则输出一个数表示最少总奖金。

数据范围
1≤n≤10000,
1≤m≤20000

输入样例:
2 1
1 2
输出样例:
201
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int M = 20000 + 10;
struct Edge{ 
   
    int v,w,next;
}edge[M];
int head[N],cnt;
    int n,m;
void add(int u,int v){ 
   
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
int vis[N],in[N],dist[N];
int q[N],hh = 0,tt = 0;
int bfs(){ 
   
    for(int i = 1;i <= n;i ++){ 
   
        if(!in[i]){ 
   
            q[tt ++] = i;
            dist[i] = 100;
        }
    }
    int cnt = 0;
    while(hh < tt){ 
   
        int t = q[hh ++];
        cnt ++;
        for(int i = head[t];~i;i = edge[i].next){ 
   
            int v = edge[i].v;
            if(dist[v] <= dist[t] + 1){ 
   
                dist[v] = dist[t] + 1;
            }
            in[v] --;
            if(!in[v])q[tt ++] = v;
        }
    }
    int res = 0;
    for(int i = 1;i <= n;i ++){ 
   
        res += dist[i];
    }
    if(cnt < n)return -1;
    return res;
}
int main(){ 
   
    cin>>n>>m;
    int x,y;
    memset(head,-1,sizeof head);
    for(int i = 0;i < m;i ++){ 
   
        cin>>x>>y;
        add(y,x);
        in[x] ++;
    }
    int t = bfs();
    if(t == -1)cout<<"Poor Xed"<<endl;
    else cout<<t<<endl;
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169089.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • dell服务器显示器fre,戴尔发布Gaming 24/27游戏显示器新品 支持144/155Hz FreeSync

    dell服务器显示器fre,戴尔发布Gaming 24/27游戏显示器新品 支持144/155Hz FreeSync访问购买页面:具体说来,24英寸机型覆有防眩光涂层(硬度3H),长宽比为16:9、支持1670万色,水平/垂直可视角度为160/170°。此外还有LEDedgelight、ComfortView、戴尔显示管理器、且兼容VESA壁挂安装。接口方面,该机型提供了2×HDMI1.4、DisplayPort、一个USB3.0上联+两个USB3.0下联、耳机…

  • 软件测试用例包括_afnetworking实现原理

    软件测试用例包括_afnetworking实现原理测试用例分层每个测试用例都有1个或多个测试步骤(List[step]),每个测试步骤对应一个API请求或其他用例的引用。从上图分析,我们可以看到testsuite中包含了3个测试用例,testca

  • PHP feof() 函数

    PHP feof() 函数

    2021年11月10日
  • 《算法图解》-9动态规划 背包问题,行程最优化

    《算法图解》-9动态规划 背包问题,行程最优化本文属于《算法图解》系列。学习动态规划,这是一种解决棘手问题的方法,它将问题分成小问题,并先着手解决这些小问题。一背包问题背包问题,在可装物品有限的前提下,尽量装价值最大的物品,如果物品数量足够大,简单的暴力穷举法是不可行的O(2ⁿ),前一章介绍了《贪婪算法》就是解决如何找到近似解,这接近最优解,但可能不是最优解。如何找到最优解呢?就是动态规划算法。动态规划先解决子问题,…

  • 大约SQL现场“这包括”与“包括在”字符串的写法

    大约SQL现场“这包括”与“包括在”字符串的写法

  • JavaScript之ES6数组排序 高逼格!

    JavaScript之ES6数组排序 高逼格!前言:针对于前端开发者来讲、数组排序的应用场景其实并不多,大多数情况下都是后台数据排序之后再返回给前端。但是很多面试题中会经常遇到数组排序的问题,经典案例有冒泡排序、插入排序、选择排序等等…逻辑性比较强硬。为了追求完美、拒绝花里胡哨,所以今天写一篇以ES6相关知识实现排序的文章、并且挂载至原型链上方便使用,希望对大家的开发有所帮助!技术点:ES6中sort()方法、箭头函数,p…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号