BZOJ 1051 最受欢迎的牛 解题报告

时间：2021-06-06 18:11:25

题目直接摆在这里！

1051: [HAOI2006]受欢迎的牛

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 4438  Solved: 2353
[Submit][Status][Discuss]

Description

　　每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。 这
种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头
牛被所有的牛认为是受欢迎的。

Input

　　第一行两个数N,M。 接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可
能出现多个A,B）

Output

　　一个数，即有多少头牛被所有的牛认为是受欢迎的。

Sample Input

3 3
1 2
2 1
2 3

Sample Output

1

HINT

100%的数据N<=10000,M<=50000

Source

[Submit][Status][Discuss]

这道题和codevs2822爱在心中类似，也是一道tarjan练手题，所以具体的tarjan板子我就不再贴出来了。

这道题的思路也可以和codevs2822一样的，使用tarjan+SPFA，但是由于本人太懒，不想再打140行代码，就换了另一种思路。

正解：tarjan缩点

具体做法：

第一步，先读入数据建边；

第二步，开始跑tarjan，别忘记在tarjan过程中要缩点，接下来的过程要用到。（所谓缩点，就是把每个点都归到一个强联通块里面，对强联通块进行操作）

第三步：根据m个边的关系，统计每个强联通块的出度。

第四步：统计出度为0的强联通块的个数，若为1，则输出次强联通块组成元素个数，否则输出0。（这里才是这道题目核心的思想，想一想为什么，其实很简单）。

先贴上代码（建议大家不要用vector这种东西，数据结构尽量手写）

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <stack>

 using namespace std;

 int get_num(){

     int num = ;

     char c;

     bool flag = false;

     while((c = getchar()) == ' ' || c == '\r' || c == '\n');

     if(c == '-')

         flag = true;

     else num = c - '';

     while(isdigit(c = getchar()))

         num = num *  + c - '';

     return (flag ? - : ) * num;

 }

 const int maxn = 1e4 + ;

 const int maxm = 5e4 + ;

 int n,m,h[maxn],sccno[maxn],scc_cnt,id[maxn],sum,r[maxn],dfn[maxn],low[maxn],dfs_clock,ans,pos;

 stack<int>s;

 struct edge{

     int fr,to,next;

 }edges[maxm << ];

 void addedge(int u,int v){

     edges[sum].fr = u;

     edges[sum].to = v;

     edges[sum].next = h[u];

     h[u] = sum++;

 }

 void init(){

     memset(id,,sizeof(id));

     memset(sccno,,sizeof(sccno));

     memset(r,,sizeof(r));

     memset(h,-,sizeof(h));

     memset(edges,,sizeof(edges));

     sum = ;

     dfs_clock = ;

     memset(dfn,,sizeof(dfn));

     memset(low,,sizeof(low));

 }

 void tarjan(int u){

     dfn[u] = low[u] = ++dfs_clock;

     s.push(u);

     for(int i = h[u];i != -;i = edges[i].next){

         edge e = edges[i];

         if(!dfn[e.to]){

             tarjan(e.to);

             low[u] = min(low[u],low[e.to]);

         }

         else if(!id[e.to])

             low[u] = min(low[u],dfn[e.to]);

     }

     if(low[u] == dfn[u]){

         scc_cnt++;

         while(true){

             int x = s.top();

             s.pop();

             sccno[scc_cnt] += ;

             id[x] = scc_cnt;

             if(x == u)break;

         }

     }

     return;

 }

 void find_tarjan(){

     for(int i = ;i <= n;++i){

         if(!dfn[i])

             tarjan(i);

     }

     return;

 }

 int main(){

     int a,b;

     init();

     n = get_num();

     m = get_num();

     for(int i = ;i <= m;++i){

         a = get_num();

         b = get_num();

         addedge(a,b);

     }

     find_tarjan();

     for(int i = ;i < sum;++i){

         int x = edges[i].fr;

         int y = edges[i].to;

         if(id[x] != id[y])

             r[id[x]]++;

     }

     ans = ;

     for(int i = ;i <= scc_cnt;++i){

         if(r[i] == ){

             if(!ans)

                 ans = sccno[i];

             else{

                 ans = ;

                 break;

             }

         }

     }

     printf("%d\n",ans);

     return ;

 }

这次解题报告就写到这里吧，NOIP倒计时两个月，祝大家能考个好成绩！

相关文章