首页 > 其他 > 详细

洛谷 P3183 [HAOI2016]食物链

时间:2020-02-13 01:13:53      阅读:66      评论:0      收藏:0      [点我收藏+]

题目传送门

解题思路:

另一个题差不多,就是本题单独一个生物不算一条食物链.

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<queue>
 5 
 6 using namespace std;
 7 
 8 int n,m,_in[100001],f[100001],_out[100001],ans;
 9 vector<int> a[100001];
10 bool vis[100001];
11 queue<int> q;
12 
13 inline void solve(int fa) {
14     q.push(fa);
15     f[fa] = 1;
16     while(!q.empty()) {
17         int u = q.front();
18         q.pop();
19         for(int i = 0;i < a[u].size(); i++) {
20             f[a[u][i]] = f[a[u][i]] + f[u];
21             _in[a[u][i]]--;
22             if(_in[a[u][i]] == 0)
23                 q.push(a[u][i]);
24         }
25     }
26 }
27 
28 int main() {
29     scanf("%d%d",&n,&m);
30     for(int i = 1;i <= m; i++) {
31         int x,y;
32         scanf("%d%d",&x,&y);
33         _in[y]++;_out[x]++;
34         a[x].push_back(y);
35         vis[y] = 1;
36     }
37     for(int i = 1;i <= n; i++) 
38         if(!vis[i])
39             solve(i);
40     for(int i = 1;i <= n; i++) 
41         if(_out[i] == 0 && vis[i])
42             ans += f[i];
43     printf("%d",ans);
44     return 0;
45 } 

 

洛谷 P3183 [HAOI2016]食物链

原文:https://www.cnblogs.com/lipeiyi520/p/12301855.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!