60分求助wa了QwQ
  • 板块P2016 战略游戏
  • 楼主loris
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/6/25 16:14
  • 上次更新2023/11/4 21:31:24
查看原帖
60分求助wa了QwQ
130104
loris楼主2021/6/25 16:14
#include<bits/stdc++.h>
using namespace std;
const int MM=3500;
int nxt[MM],head[MM],t[MM],f[MM][2],out[MM],l[MM][2],tot,n,m;
void add(int u,int v)
{
	nxt[++tot]=head[u];
	head[u]=tot;
	t[tot]=v;
}
void dfs(int i,int fa)
{
	if(f[i][0]>=0&&f[i][1]>=0)return ;
	if(out[i]==1&&fa!=n+1)
	{
		f[i][0]=0,f[i][1]=1;
		return ;
	}	
	int a=0,b=0;
	for(int j=head[i];j;j=nxt[j])
	{
		if(t[j]==fa)continue ;
		dfs(t[j],i);
		a+=f[t[j]][1];
		b+=min(f[t[j]][0],f[t[j]][1]);
	}
	f[i][1]=b+1;
	f[i][0]=a;
	return ;
}
int main()
{
	cin>>n;int q;
	for(int i=0;i<=n;i++)
	{
		f[i][0]=f[i][1]=-1;
	}
	for(int i=0;i<=n-1;i++)
	{
		cin>>q>>m;out[i]=m;
		for(int j=1;j<=m;j++)
		{
			cin>>q;
			add(i,q);
		}
	}
	dfs(0,n+1);
	cout<<min(f[0][0],f[0][1]);
	return 0;
} 
2021/6/25 16:14
加载中...