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

题目直接摆在这里!

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倒计时两个月,祝大家能考个好成绩!

上一篇:习题:codevs 2822 爱在心中 解题报告


下一篇:第9章 Linux进程和信号超详细分析