好贷网好贷款

拓扑排序 hdu 2647 Reward

发布时间:2016-12-4 9:56:26 编辑: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面向对象设计 构造函数设计】

相关文章

相关评论