# Reward

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6336    Accepted Submission(s): 1958

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
2680
2112
1142
2729

3 3

1 2

2 3

1 3

3 2 1 2 1 3 2665

3 1 1 2 2665

``````#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<int>map[10005];
int top_sort(int n)
{
queue<int>s;
for(int i=1;i<=n;i++)
if(in[i]==0)
s.push(i);
int count=0;
while(!s.empty())
{
int x=s.front();
s.pop();
count++;
for(int i=0;i<map[x].size();i++)
{
in[map[x][i]]--;
if(in[map[x][i]]==0)
{
s.push(map[x][i]);
}
}
}
if(count!=n)
return -1;
int sum=0;
for(int i=1;i<=n;i++)
return sum;
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
memset(in,0,sizeof(in));
memset(map,0,sizeof(map));
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d %d",&a,&b);
map[b].push_back(a);
in[a]++;
}
printf("%d\n",top_sort(n));
}
return 0;
}``````

原文作者：拓扑排序
原文地址: https://blog.csdn.net/su20145104009/article/details/50284919
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。