比赛 防止浮躁的小练习v0.7 评测结果 AAAAAAAAAA
题目名称 食物链 最终得分 100
用户昵称 kxxy 运行时间 1.715 s
代码语言 C++ 内存使用 2.99 MiB
提交时间 2016-10-27 16:09:21
显示代码纯文本
  1. //草<->1 兔<->2 狐<->3 鼠<->4 猫头鹰<->5
  2. //吃虫的鸟<->6 蜘蛛<->7 蛇<->8 青蛙<->9 食草昆虫<->10.
  3. #include<iostream>
  4. #include<cstdio>
  5. #include<vector>
  6. #include<queue>
  7. using namespace std;
  8. const int maxx=100010;
  9. int in[maxx],out[maxx];
  10. long long cnt[maxx];
  11. vector<int>v[maxx];
  12. queue<int>q;
  13. int n,m,a,b;
  14. int main()
  15. {
  16. freopen("chain_2016.in","r",stdin);
  17. freopen("chain_2016.out","w",stdout);
  18. cin>>n>>m;
  19. for(int i=1;i<=n;i++)
  20. v[i].clear();
  21. for(int i=1;i<=m;i++)
  22. {
  23. cin>>a>>b;
  24. v[a].push_back(b);
  25. in[b]++;
  26. out[a]++;
  27. }
  28. long long ans=0;
  29. for(int i=1;i<=n;i++)
  30. if(!in[i])
  31. {
  32. cnt[i]=1;
  33. q.push(i);
  34. if(!out[i])
  35. ans--;
  36. }
  37. while(!q.empty())
  38. {
  39. int c=q.front();
  40. q.pop();
  41. for(int i=0;i<v[c].size();i++)
  42. {
  43. cnt[v[c][i]]+=cnt[c];
  44. in[v[c][i]]--;
  45. if(!in[v[c][i]])
  46. q.push(v[c][i]);
  47. }
  48. }
  49. for(int i=1;i<=n;i++)
  50. if(!out[i])
  51. ans+=cnt[i];
  52. cout<<ans<<endl;
  53. return 0;
  54. }