首先,我不会
然后,我旁边的大佬,ta一看,原来是二分图(年轻人,不讲武德)
直接看:玩具是和空位置形成一个二分图,可以对于每一个有玩具的点先跑一个dfs找边(放心,只有50,不会T掉)
最后跑一个匈牙利算法
然后我们就可以贴代码了:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,head[51],xia[5001],tot,to[5001],T; int head2[51],xia2[5001],to2[5001],tot2,m; int match[51],qu[51]; bool zha[51],ok[51]; void dfs(int x,int ti,int st){ if(ti == T+1) return ; ok[x] = 1; if(!zha[x]) { xia[++tot] = head[st]; head[st] = tot,to[tot] = x; } for(int i(head2[x]);i;i=xia2[i]){ int j(to2[i]); if(ok[j]) continue; dfs(j,ti+1,st); } } bool dfs2(int x) { ok[x] = 1; for(int i(head[x]);i;i=xia[i]) { int j=to[i]; if(ok[match[j]]) continue; if(!match[j]||dfs2(match[j])){ match[j] = x; return 1; } } return 0; } int main(){ scanf("%d%d",&n,&T);int x,ans(0); for(int i(2);i<=n;++i){ scanf("%d",&x); ++x; xia2[++tot2] = head2[i]; head2[i] = tot2,to2[tot2] = x; xia2[++tot2] = head2[x]; head2[x] = tot2,to2[tot2] = i; } scanf("%d",&m); for(int i(1);i<=m;++i){ scanf("%d",&qu[i]);++qu[i];zha[qu[i]] = 1; } for(int i(1);i<=n;++i){ if(zha[i]==1) { memset(ok,0,sizeof(ok)); dfs(i,0,i); } } memset(ok,0,sizeof(ok)); for(int i(1);i<=m;++i){ if(!match[qu[i]]&&dfs2(qu[i])) { ++ans; memset(ok,0,sizeof(ok)); } } printf("%d",ans); return 0; }