Reward
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7986 Accepted Submission(s): 2540
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
题意：
有n个工人，有k中关系
在接下来k行中，有a,b两个数,表示a的工资要高于b，n个人中最低工资为888；
若能满足这k个关系，则输出n个人的总工资
若不能满足，则输出-1
思路
拓扑排序
#include<iostream>
#include<list>
#include<queue>
using namespace std;
class Graph
{
public:
int V;
int *vexWeight; //顶点的值
list<int> *adj;
queue<int> q;
int *indegree;
Graph(int V);
~Graph();
void addEdge(int v,int w);
bool topological_sort(int src);
};
Graph::Graph(int V){
this->V=V;
vexWeight = new int[V];
adj = new list<int>[V];
indegree = new int [V];
for(int i=0;i<V;i++)
indegree[i]=0;
}
Graph::~Graph(){
delete []adj;
delete []indegree;
delete []vexWeight;
}
void Graph::addEdge(int v,int w)
{
adj[v].push_back(w);
++indegree[w];
}
bool Graph::topological_sort(int src)
{
for(int i=0;i<V;i++)
if(indegree[i]==0)
q.push(i),vexWeight[i]=src;
int count=0;
while(!q.empty())
{
int v=q.front();
q.pop();
//cout<<v<<" ";
++count;
list<int>::iterator it=adj[v].begin();
for(;it!=adj[v].end();it++)
if(!(--indegree[*it]))
q.push(*it),vexWeight[*it]=vexWeight[v]+1;
}
if(count<V)
return false;
else
return true;
}
int main(){
int n,k,a,b;
while(cin>>n>>k){
Graph g(n);
for(int i=0;i<k;i++){
cin>>a>>b;
g.addEdge(b-1,a-1);
}
if(g.topological_sort(888)){
int sum=0;
for(int i=0;i<n;i++){
sum += g.vexWeight[i];
}
cout<<sum<<endl;
}
else
cout<<"-1"<<endl;
}
return 0;
}