菜单

2266. [HAOI201陆]食品链 纪念化

2019年4月4日 - 生物学

2266. [HAOI2016]食物链

★   输入文件:chain_2016.in   输出文件:chain_2016.out   不难相比较
时间限定:一 s   内部存款和储蓄器限制:12八 MB

【标题叙述】

如图所示为某生态系统的食品网示意图,据图回答第贰小题。

生物学 1

一.数一数,在那么些食品网中有几条食品链(   )

现行反革命给您n个物种和m条能量流动涉及,求此中的食品链条数。

物种的名号为从1到n编号,m条能量流动涉及形如

a1 b1

a2 b2

a3 b3

……

am−1 bm−1

am bm

当中ai bi表示能量从物种ai流向物种bi。

【输入格式】

先是行多个正整数n和m。

接下去m行每行五个整数ai bi表示m条能量流动涉及。

(数据保证输入数据符合生物学特点,且不会有双重的能量流动涉及出现)

【输出格式】

2个平头即食物网中的食品链条数。

【样例输入】

10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 8
7 6
7 9
8 5
9 8
10 6
10 7
10 9

【样例输出】

9

【样例解释】

不畏地点标题叙述1生物学,的要命图。

次第物种的数码顺序为:

草<->一 兔<->2 狐<->三 鼠<->四 猫头鹰<->伍吃虫的鸟<->六 蜘蛛<->7 蛇<->八 青蛙<->九食草昆虫<->十。

【数据范围】

1≤n≤100000,0≤m≤200000。

【来源】

HAOI201陆晚上先是题 部分题面由ck进行调整

//单点不算食物链
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;
const int N=200010;

int U[N>>1],V[N>>1],V0[N>>1];
int head[N>>1];
int ans[N>>1];
bool vis[N>>1];
int now=1;
int n,m,js;
int answer;
struct node{
    int u,v,nxt;
}E[N];

inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}

inline void add(int u,int v)
{
    E[now].u=u;
    E[now].v=v;
    E[now].nxt=head[u];
    head[u]=now++;
}

void dfs(int start)
{
    vis[start]=1;
    if(!U[start])
    {
        answer++;
        return ;
    }
    for(int i=head[start];~i;i=E[i].nxt)
        if(!vis[E[i].v])
            dfs(E[i].v),
            vis[E[i].v]=0;
}

int main()
{
    freopen("chain_2016.in","r",stdin);
    freopen("chain_2016.out","w",stdout);
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
        head[i]=-1;
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        U[u]++,V[v]++;
        add(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!V[i]&&U[i])
            V0[++js]=i;
    for(int i=1;i<=js;i++)
        dfs(V0[i]);
    printf("%d",answer);        

    return 0;
}
/*
10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 8
7 6
7 9
8 5
9 8
10 6
10 7
10 9
*/

 回想化搜索:

//单点不算食物链
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;
const int N=200010;

int U[N>>1],V[N>>1],V0[N>>1];
int head[N>>1];
int ans[N>>1];
bool vis[N>>1];
int now=1;
int n,m,js;
int answer;
struct node{
    int u,v,nxt;
}E[N];

inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}

inline void add(int u,int v)
{
    E[now].u=u;
    E[now].v=v;
    E[now].nxt=head[u];
    head[u]=now++;
}

int dfs(int start)
{
    if(!U[start])
        ans[start]++;
    for(int i=head[start];~i;i=E[i].nxt)
        if(ans[E[i].v])
            ans[start]+=ans[E[i].v];
        else
            ans[start]+=dfs(E[i].v);
    return ans[start];
}

int main()
{
    freopen("chain_2016.in","r",stdin);
    freopen("chain_2016.out","w",stdout);
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
        head[i]=-1;
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        U[u]++,V[v]++;
        add(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!V[i]&&U[i])
            V0[++js]=i;
    for(int i=1;i<=js;i++)
        answer+=dfs(V0[i]);

    printf("%d",answer);        

    return 0;
}

 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图