当前位置：网站首页>hdu 2647 Reward（拓扑排序)

hdu 2647 Reward（拓扑排序)

2022-08-09 18:34:00 【51CTO】

题目： http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=23269

Description

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

让最小的人收到888money，比他大的加1，按照拓扑排序增长，最后求出总资金。

       
       #include <iostream>
       
       #include <cstdio>
       
       #include <cstring>
       
       using 
       
       namespace 
       
       std;
       
       const 
       
       int 
       
       maxn
       
       =
       
       2e4
       
       +
       
       5,
       
       N
       
       =
       
       maxn
       
       /
       
       2;
       
       int 
       
       head[
       
       N],
       
       indeg[
       
       N],
       
       n,
       
       m,
       
       ip;
       
       struct 
       
       node{
       
       int 
       
       to,
       
       next;
       
}
       
       edge[
       
       maxn];
       
       int 
       
       money[
       
       maxn];
       
       void 
       
       init(){
       
       ip
       
       =
       
       0;
       
       memset(
       
       money,
       
       0,
       
       sizeof(
       
       money));
       
       memset(
       
       head,
       
       -
       
       1,
       
       sizeof(
       
       head));
       
       memset(
       
       indeg,
       
       0,
       
       sizeof(
       
       indeg));
       
}
       
       bool 
       
       topo(){
       
       int 
       
       que[
       
       maxn],
       
       iq
       
       =
       
       0;
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       i
       
       ++) 
       
       if(
       
       indeg[
       
       i]
       
       ==
       
       0){ 
       
       que[
       
       iq
       
       ++]
       
       =
       
       i;  
       
       money[
       
       i]
       
       =
       
       888; } 
       
       //cout<<i<<endl; }
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       iq;
       
       i
       
       ++){
       
       for(
       
       int 
       
       k
       
       =
       
       head[
       
       que[
       
       i]];
       
       k
       
       >-
       
       1;
       
       k
       
       =
       
       edge[
       
       k].
       
       next){
       
       indeg[
       
       edge[
       
       k].
       
       to]
       
       --;
       
       if(
       
       indeg[
       
       edge[
       
       k].
       
       to]
       
       ==
       
       0){
       
       que[
       
       iq
       
       ++]
       
       =
       
       edge[
       
       k].
       
       to; 
       
       //que里存储的是节点，head存储的是边的编号
       
       money[
       
       edge[
       
       k].
       
       to]
       
       =
       
       money[
       
       que[
       
       i]]
       
       +
       
       1;
       
             }
       
         }
       
    }
       
       if(
       
       iq
       
       ==
       
       n) 
       
       return 
       
       1;
       
       return 
       
       0;
       
}
       
       void 
       
       addedge(
       
       int 
       
       u,
       
       int 
       
       v){
       
       edge[
       
       ip].
       
       to
       
       =
       
       v;
       
       edge[
       
       ip].
       
       next
       
       =
       
       head[
       
       u];
       
       head[
       
       u]
       
       =
       
       ip
       
       ++;
       
       indeg[
       
       v]
       
       ++;
       
}
       
       int 
       
       main()
       
{
       
       //freopen("cin.txt","r",stdin);
       
       int 
       
       a,
       
       b;
       
       while(
       
       cin
       
       >>
       
       n
       
       >>
       
       m){
       
       init();
       
       while(
       
       m
       
       --){
       
       scanf(
       
       "%d %d",
       
       &
       
       a,
       
       &
       
       b);
       
       addedge(
       
       b,
       
       a);
       
        }
       
       int 
       
       pj
       
       =
       
       topo();
       
       if(
       
       pj
       
       ==
       
       0){  
       
       printf(
       
       "-1\n");  
       
       continue; }
       
       int 
       
       ans
       
       =
       
       0;
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       i
       
       ++){
       
       ans
       
       +=
       
       money[
       
       i];
       
        }
       
       printf(
       
       "%d\n",
       
       ans);
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15746559/5560566

当前位置：网站首页>hdu 2647 Reward（拓扑排序)

hdu 2647 Reward（拓扑排序)

边栏推荐

猜你喜欢

随机推荐