拓扑排序 hdu 2647 Reward

发布时间:2014-10-22 13:48:31编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"拓扑排序 hdu 2647 Reward",主要涉及到拓扑排序 hdu 2647 Reward方面的内容,对于拓扑排序 hdu 2647 Reward感兴趣的同学可以参考一下。

2011ACM/ICPC亚洲区中国大陆5个赛区信息汇集 Reward Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 868    Accepted Submission(s): 260 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 #include<stdio.h> #include<string.h> #include<malloc.h> struct node {     int data;     struct node *next; }; int getmax(int a,int b) { return a>b?a:b; } struct node a[10010];   int flag=1; int mon[10010];  void  Topsort(int T) {     int i,sum=0,j;      for(i=1;i<=T;i++)   { struct node *p; j=1; while(a[j].data!=0) j++; if(j>T)  flag=0;      sum+=mon[j];  a[j].data=-1; for(p = a[j].next;p!=NULL;p=p->next) { a[p->data].data --; mon[p->data]=getmax(mon[j]+1,mon[p->data]); }   } if(flag==1) printf("%d\n",sum); else printf("-1\n");   } int main() {     int T,m,i,x,y;     while(scanf("%d%d",&T,&m)!=EOF)     { flag=1; memset(mon,0,sizeof(mon)); for(i=1;i<=T;i++)         {             a[i].data=0;             a[i].next=NULL;         }   while(m--) {                    struct node *q,*p;             p=(struct node*)malloc(sizeof(struct node));             scanf("%d%d",&x,&y); if(x!=y) { a[x].data++; p->data=x; p->next=NULL; q=&a[y]; if(q->next==NULL) q->next=p; else { p->next=q->next; q->next=p;                      } } } for(i=1;i<=T;i++) { mon[i]=888; } Topsort(T);     }          return 0; }  


上一篇:拓扑排序hdu&nbsp;3342&nbsp;Legal&nbsp;or&nbsp;Not
下一篇:【Java面向对象设计 构造函数设计】

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款