HAOI2016 食物鍊

#某鹹魚紅紅火火恍恍惚惚練記憶化搜尋的日記

這道題其實和滑雪（SHOI2002）本質是一樣的。。

是以現已加入記憶化搜尋練習套餐√

思路是dfs，開個數組存搜過的，然後瞎暴力就可以了

但是注意可能會有獨立出來的點和圖，是以要統計入度和出度

遇到入度為零的需要新一波dfs，遇到入度出度都為零的單點也要記為一條鍊

破程式：

#include<cstdio>
#include<iostream>
using namespace std;

const int MAXN=100003,MAXM=200003;

struct node{
    int from,to;
};

int n,m,cnt,ans=0;
int f[MAXN],ru[MAXN],chu[MAXN],head[MAXM];
node map[MAXM*2];

void add(int x,int y)    //鄰接表加邊
{
    map[++cnt].from=head[x];
    map[cnt].to=y;
    head[x]=cnt;
}

int r() //讀入優化
{ 
    int f=1,p=0;
    char c=getchar(); 
    while(c>'9'||c<'0')
      {
        if(c=='-') f=-1;
        c=getchar();
      } 
    while(c>='0'&&c<='9')
      {
         p=p*10+c-'0';
         c=getchar();
      } 
    return f*p; 
}

int dfs(int u)    //想寫dps...
{
    if(f[u]) return f[u];
    int ans=0;
    if(!chu[u]&&ru[u]) return 1;
    for(int i=head[u];i;i=map[i].from)
    {
        int next=map[i].to;
        ans+=dfs(next);
    }
    f[u]=ans;
    return ans;
}

int main()
{
    n=r();m=r();
    for(int i=1;i<=m;i++)
    {
        int a,b;
        a=r();b=r();
        add(a,b);
        chu[a]++;ru[b]++;    //計入度和出度
    }

    for(int i=1;i<=n;i++)
    {
        if(!ru[i])    //找到新的一塊r啦
            ans+=dfs(i);
    }
    cout<<ans;    //完成w
    
    return 0;
}
           

最後，一個挺傻白甜的dps格式？

int dps(int x)
{
	if(f[x]) return x;
	int t=0;    //不一定從0開始，反正能做到通過遞歸計數就好
	for()
	{
		t+=dps();
	}
	f[x]=t;
	return t;
} 
           

（菜到沒眼看.jpg）