HDU 2647 Reward 【拓扑排序反向建图+队列】

HDU 2647 Reward 【拓扑排序反向建图+队列】

题目 Reward

Dandelion’s uncle is a boss of a factory. As the spring festival is coming , he wants to distribute rewards to his workers. Now he has a trouble about how to distribute the rewards. 
The workers will compare their rewards ,and some one may have demands of the distributing of rewards ,just like a’s reward should more than b’s.Dandelion’s unclue wants to fulfill all the demands, of course ,he wants to use the least money.Every work’s reward will be at least 888 , because it’s a lucky number.

Input

One line with two integers n and m ,stands for the number of works and the number of demands .(n<=10000,m<=20000) 
then m lines ,each line contains two integers a and b ,stands for a’s reward should be more than b’s.

Output

For every case ,print the least money dandelion ‘s uncle needs to distribute .If it’s impossible to fulfill all the works’ demands ,print -1.

Sample Input

2 1
1 2
2 2
1 2
2 1

Sample Output

1777
-1

 

注意初始化~~ 

#include<iostream>
#include<cstdio>     //EOF,NULL
#include<cstring>    //memset
#include<cstdlib>    //rand,srand,system,itoa(int),atoi(char[]),atof(),malloc
#include<cmath>           //ceil,floor,exp,log(e),log10(10),hypot(sqrt(x^2+y^2)),cbrt(sqrt(x^2+y^2+z^2))
#include<algorithm>  //fill,reverse,next_permutation,__gcd,
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<utility>
#include<iterator>
#include<iomanip>             //setw(set_min_width),setfill(char),setprecision(n),fixed,
#include<functional>
#include<map>
#include<set>
#include<limits.h>     //INT_MAX
#include<bitset> // bitset<?> n
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
#define all(x) x.begin(),x.end()

#define readc(x) scanf("%c",&x)
#define read(x) scanf("%d",&x)
#define read2(x,y) scanf("%d%d",&x,&y)
#define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define print(x) printf("%d\n",x)
#define mst(a,b) memset(a,b,sizeof(a))
#define pb(x) push_back(x)
#define lowbit(x) x&-x
#define lson(x) x<<1
#define rson(x) x<<1|1
const int INF =0x3f3f3f3f;
const int mod = 1e9+7;
const int MAXN = 10010;
int n,m;
int a,b;
int in[MAXN];
int sum,cnt;
int price[MAXN];
vector<int>Edge[MAXN];
vector<int> ans;
queue<int> q;

void Init(){
  for(int i = 1;i <= n;i++){
      Edge[i].clear();
  }
  memset(in,0,sizeof in);
  while(!q.empty())  q.pop();
  sum = cnt = 0;
}

int main(){
  while(read2(n,m)!=EOF){
      Init();

      for(int i = 0 ; i < m;i++){
        read2(a,b);
        Edge[b].push_back(a);   //反向建图
        in[a] ++;
      }

      for(int i = 1 ;i <= n ;i++){
         if(in[i] == 0){
           q.push(i);
           price[i] = 888;
         }
      }
      
      
      while(!q.empty()){
          int p = q.front();
          sum += price[p];
          cnt++;
          q.pop();
          for(int i = 0; i < Edge[p].size(); i++){
             int y  = Edge[p][i];
             in[y] --;
             price[y] = price[p]+1;
             if(in[y] == 0){
               q.push(y);
             }
          }
      }
      if(cnt < n){
        printf("-1\n");
      }
      else{
        print(sum);
      }
  }


}

 

转载于:https://www.cnblogs.com/llke/p/10780133.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • 金山词霸2009牛津版完整激活成功教程版+绿色精简版下载

    金山词霸2009牛津版完整激活成功教程版+绿色精简版下载山软件推出了最新的《金山词霸2009牛津版》了!这次金山词霸与牛津合作,一次性增加6本牛津词典,这在牛津在全球的翻译软件合作伙伴中也属首次,实属不容易呢,可以说提升了金山词霸在翻译软件类中的权威和经典的形象了。    这次《金山词霸2009牛津版》里面内置了6本牛津词典:《新牛津英汉双解大词典》、《新牛津美语大词典》、《牛津英语习语词典》、《牛津短语动词词典》、《牛津英语搭配词典》、《牛津英语同义

  • 几款网络测试工具总结报告_网络端口测试工具

    几款网络测试工具总结报告_网络端口测试工具几款网络测试工具总结ping命令以前是一个很好用并且常用的网络测试工具,它是基于ICMP协议,但是出于网络安全等因素,大部分网络环境以及云环境可能都会禁止ICMP协议,所以在工作中,我们必须掌握一些

  • win10命令行强制删除文件_win10cmd强制删除文件夹

    win10命令行强制删除文件_win10cmd强制删除文件夹提醒:以下方法文件永久删除,常规方法无法恢复,慎用,慎用,慎用针对电脑中不知什么软件生成的无用文件,使用修改文件夹属性的可视化方法,试过多次都没有成功,后通过执行命令行删除文件。步骤如下:(1)

  • 单点登录原理与简单实现(单点登录原理与简单实现)

    单点登录(SingleSignOn),简称为SSO,是目前比较流行的企业业务整合的解决方案之一。SSO的定义是在多个应用系统中,用户只需要登录一次就可以访问所有相互信任的应用系统。以下是个人查询资料的借鉴及对接某大型互联网公司单点系统后的一个总结和理解一、首先了解下单系统登录机制1、http无状态协议  web应用采用browser/server架构,http作为通信协议。http是无状态协…

  • 部署禅道至外网

    部署禅道至外网结论:采用Cpolar映射工具和netsh命令netsh命令可以将对本地/局域网的某个端口的请求转发给本地/局域网的另一端口接收处理,假设利用Cpolar映射工具将本地的12345端口映射到外网,再利用netsh命令将本地12345端口转发到192.168.10.188的8000端口,这样,我在外网用http请求本地12345端口时,实际上是在请求禅道(192.168.10.188:8000)网址结论:可行工具:cpolar内网穿透工具和一台内网开着的电

  • python初级:基础知识学习-循环、列表、元组、集合、字典

    python初级:基础知识学习-循环、列表、元组、集合、字典

发表回复

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

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