Reward
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 9800 Accepted Submission(s): 3131
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
题目重现：
问题描述
蒲公英的叔叔是工厂的老板。 随着春节来临，他想向他的工人分发奖励。 现在他有分享奖励的麻烦。工作人员会比较他们的回报，有的可能会有分配奖励的要求，就像一个奖励应该超过b's.蒲公英的无礼想要完成所有的要求，当然，他想使用最少的钱。每个工作 奖励至少是888，因为这是一个幸运数字。 思路：
拓扑排序，求出每一层上的节点，对于每一层比上一层的钱数多一，至于无法确定的情况即是出现环的情况、、直接输出-1。
怎样判断是哪一层？！我们进行删边的时候当前节点的入读为0，被删掉后的入度为零的节点一定比当前节点的层数多1.我们用这一层关系来判断、也就是这样ceng[edge[i].to]=ceng[x]+1、、、
代码：
#include#include #include #include #include #include #define N 20100#define money 888using namespace std;queue q;long long anss;int n,m,x,y,s,in[N],tot,sum,head[N],ans[N];int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;}struct Edge{ int from,to,next;}edge[N];int add(int x,int y){ tot++; edge[tot].to=y; edge[tot].next=head[x]; head[x]=tot;}void begin(){ s=0,sum=0,tot=0;anss=0; memset(in,0,sizeof(in)); memset(ans,0,sizeof(ans)); memset(head,0,sizeof(head)); memset(edge,0,sizeof(edge));}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { begin(); for(int i=1;i<=m;i++) { x=read(),y=read(); add(y,x),in[x]++; } for(int i=1;i<=n;i++) if(in[i]==0) q.push(i),ans[i]=0; while(!q.empty()) { x=q.front(),q.pop(),sum++; for(int i=head[x];i;i=edge[i].next) { int t=edge[i].to; in[t]--; if(in[t]==0) q.push(t),ans[t]=ans[x]+1; } } if(sum!=n) printf("-1\n"); else { for(int i=1;i<=n;i++) anss+=money+ans[i]; printf("%lld\n",anss); } } return 0;}