求教问题(真弱鸡)
  • 板块学术版
  • 楼主Zonebulk
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/11/27 19:31
  • 上次更新2023/11/3 23:26:03
查看原帖
求教问题(真弱鸡)
305329
Zonebulk楼主2021/11/27 19:31

P3183 [HAOI2016]食物链 如果求最长食物链所包含的生物数量的话 我用的dfs,但是一直wa,求各位大佬看看

#include<bits/stdc++.h>
using namespace std;
#define maxn 1005 
#define maxm 1005
int out[maxn],in[maxn];
int u[maxm], v[maxm];
int f[1005];
struct Edge{
	int nxt, to;
}e[maxm];
int head[maxn], cnt;
void addEdge(int u,int to)
{
    e[++cnt].nxt=head[u];//上一条以u为起点的边
    e[cnt].to=to;
    head[u]=cnt;//标号,标记最后一次出现以u为起点的边
}
int dfs(int x)
{
    int max_length=0;
    if(f[x]>0)
    return f[x];
    if(out[x]==0)
    {
        f[x]=1;
        return f[x];
    }
    //cout<<"running..."<<endl;
    for(int i=head[x];i;i=e[i].nxt)
    {
        //cout<<max_length<<endl;
        max_length=max(max_length,dfs(e[i].to));
    }
    f[x]=max_length+1;
    //cout<<f[i]<<" "<<i<<endl;
    return max_length+1;
}
int main()
{
    int n,m;
    while(cin>>n)
    {
        memset(f,0,sizeof(f));
        memset(e,0,sizeof(e));
        int ans=0;
        cin>>m;
        for (int i = 1; i <=m; i++)
        {
            cin>>u[i]>>v[i];
            addEdge(u[i],v[i]);
            out[u[i]]++;
            in[v[i]]++;
        }
        for (int i = 1; i <=n; i++)
        {
            /* code */
            if(in[i]==0&&out[i]!=0)
            {
                //cout<<i<<endl;
                ans=max(ans,dfs(i));
            }
        }
        // cout<<head[1]<<" "<<e[head[1]].to<<" "<<e[head[1]].nxt<<endl;
        // cout<<f[1]<<f[2]<<f[3]<<f[4]<<endl;
        // cout<<dfs(1)<<endl;
        cout<<ans<<endl;
    }
    system("pause");
    return 0;
}
2021/11/27 19:31
加载中...