Reward
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 9548 Accepted Submission(s): 3065
Problem 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
Author
dandelion
Source
曾是惊鸿照影来
Recommend
yifenfei | We have carefully selected several similar problems for you:
3342
1811
2680
2112
2094
Statistic |
Submit |
Discuss |
Note
Home | TopHangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2017 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
思路：关键只有两个因素，点和等级，所以可以用pair<>,重载在队列中哦。
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define fi first
#define se second
typedef long long LL;
using namespace std;
const int MAX_N=10000+11;
int in[MAX_N]; //记录每个点的入度
vector<int> edge[MAX_N]; //邻接表
int n,m;
LL topo()
{
LL ans=0; //需要发的总钱数
queue<pair<int,int> > Q; //第一个参数表示点，第二个参数表示等级，等级较低钱也较少
for(int i=1;i<=n;i++)
{
if(in[i]==0)
{
Q.push(make_pair(i,0)); //入度为0，入队列
in[i]=-1;
}
}
while(!Q.empty() )
{
int pos=Q.front() .fi;
int base=Q.front() .se;
Q.pop() ;
ans+=888+base;
for(int i=0;i<edge[pos].size() ;i++)
{
int ne=edge[pos][i]; //表示点pos的邻接点
in[ne]--; //更新入度
if(in[ne]==0)
{
Q.push(make_pair(ne,base+1)); //等级比pos高一级
in[ne]=-1;
}
}
}
for(int i=1;i<=n;i++) //循环判断一次看是否存在有向环 ，存在则返回-1，
{
if(in[i]!=-1)
return -1;
}
return ans;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=n;i++)
{
in[i]=0;
edge[i].clear() ; //清空
}
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
in[a]++; //说明a的等级较高，a的入度加1
edge[b].push_back(a); //建边（即邻接表）
}
printf("%lld\n",topo());
}
return 0;
} Adminis
Reward
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 9548 Accepted Submission(s): 3065
Problem 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
Author
dandelion
Source
曾是惊鸿照影来
Recommend
yifenfei | We have carefully selected several similar problems for you:
3342
1811
2680
2112
2094
Statistic |
Submit |
Discuss |
Note
Home | TopHangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2017 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Adminis
转载请注明原文地址: https://www.6miu.com/read-54488.html
