Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 13509 Accepted Submission(s): 4314
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 1811 2680 2112 2729 分析： a b：表示a的钱应该比b多，基本工资是888，所以a最少是889 坑点： 1.必须使用邻接表存图，邻接矩阵会超内存 2.可能存在多条拓扑路径，所以不能最后直接算总工资（有点没有说明白，就是有的人工资可以和其他人一样，看下面的两组数据就知道了） 数据： 5 51 22 34 52 34 5答案：44445 41 22 52 44 3答案：4446 所以我们队列里面得存结构体！！！ code： #include<stdio.h> #include<iostream> #include<math.h> #include<string.h> #include<set> #include<map> #include<list> #include<queue> #include<algorithm> using namespace std; typedef long long LL; int mon1[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31}; int mon2[13]= {0,31,29,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}}; int getval() { int ret(0); char c; while((c=getchar())==' '||c=='\n'||c=='\r'); ret=c-'0'; while((c=getchar())!=' '&&c!='\n'&&c!='\r') ret=ret*10+c-'0'; return ret; } #define max_v 10005 int indgree[max_v]; struct node { int index,v; node(int x,int y) { index=x; v=y; } }; vector <int> vv[max_v]; int n,m; LL sum; queue<node> q; int tpsort() { sum=0; while(!q.empty()) q.pop(); for(int i=1;i<=n;i++) { if(indgree[i]==0) q.push(node(i,888)); } int c=0; int flag=0; int p1,p2; while(!q.empty()) { if(q.size()>1) flag=1; p1=q.front().index; p2=q.front().v; q.pop(); c++; sum+=p2; for(int i=0;i<vv[p1].size();i++) { indgree[vv[p1][i]]--; if(indgree[vv[p1][i]]==0) q.push(node(vv[p1][i],p2+1)); } } /* 拓扑完之后，存在没有入队的点，那么该点就一定是环上的 */ if(c!=n)//存在环 return 1; else if(flag)//能拓扑但存在多条路 return 0; return -1;//能拓扑且存在唯一拓扑路径 } int main() { int x,y; while(~scanf("%d %d",&n,&m)) { memset(indgree,0,sizeof(indgree)); for(int i=1;i<=n;i++) { vv[i].clear(); } int flag=-1; for(int i=0;i<m;i++) { scanf("%d %d",&y,&x); if(count(vv[x].begin(),vv[x].end(),y)==0)//防止重边 { vv[x].push_back(y); indgree[y]++; } if(count(vv[y].begin(),vv[y].end(),x)!=0)//环的一种 { flag=1; } } flag=tpsort(); if(flag==1) { printf("-1\n"); }else { printf("%lld\n",sum); } } }
