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)


相关推荐

  • 如何在电脑上画漫画 0基础_零基础学电脑快速入门

    如何在电脑上画漫画 0基础_零基础学电脑快速入门零基础怎么学漫画手绘?手绘漫画入门教程!想要创作手绘漫画,最重要的并不是画工技术,最重要的是学会如何讲故事,学习如何画分镜,提升个人在视频艺术方面的审美观,顺便一提,实际上天赋也是很重要的一点。当一个人的审美观达到一定程度时,对于创作本身理解的思维差异便于一般人不同了,一般人以为创作很简单,并不知道创作的难点,以为创作就是想写什么就写什么。日本画师Aちき的作品如果大家想要学习绘画的话,可…

  • Java list foreach_java的foreach

    Java list foreach_java的foreach例子://使用com.google.guava包创建集合List<String>list=Lists.newArrayList(“a”,”b”,”c”,”d”);//1、正常遍历list.forEach(item->System.out.println(item));//2、根据条件遍历list.forEach…

  • web实现QQ第三方登录「建议收藏」

    web实现QQ第三方登录「建议收藏」开放平台-web实现QQ第三方登录应用场景web应用通过QQ登录授权实现第三方登录。操作步骤1注册成为QQ互联平台开发者,http://connect.qq.com/2准备一个可访问的域名,

  • 傅里叶级数与傅里叶变换公式推导「建议收藏」

    傅里叶级数与傅里叶变换公式推导「建议收藏」首先,傅里叶分析是指把一个周期或非周期函数展开成一个个三角函数的叠加,如果是对其还没有基本概念的,可以看看傅里叶分析之掐死教程,这篇文章不依赖数学公式却又十分透彻地讲述了傅里叶分析的基本概念,十分值得一读。但如果先深入探讨其中的数学由来,接下来会讲述详细的数学推导。傅里叶级数三角函数系的正交性三角函数系:{1,sinx,cosx,sin2x,cos2x,…,sinnx,cosnx,…},它由无数个sinnx和cosnx组成,其中n=0,1,2,…。正交性:∫−ππsin⁡nxcos⁡mxdx=0,

  • java axis_Java 使用Axis实现WebService实例

    java axis_Java 使用Axis实现WebService实例在上一篇WebService实例中,基于jdk1.6以上的javax.jws发布webservice接口。这篇博文则主要用eclipse/myeclipse使用axis插件进行发布和调用WebService。1.下载axis,并解压到tomcat/webapps目录下2.在tomcat部署axis2启动tomcat,可以看到多了个axis2文件在浏览器输入:http://localho…

  • HDU 1026 Ignatius and the Princess I 迷宫范围内的搜索剪枝问题

    HDU 1026 Ignatius and the Princess I 迷宫范围内的搜索剪枝问题

发表回复

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

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