P1041 传染病控制
发布时间:2020-12-15 07:41:12 所属栏目:Java 来源:网络整理
导读:? ? 倍感自己傻逼 错的地方极其智障,一定不会犯了 打死不用vectorXD #includebits/stdc++.h using namespace std; int mp[ 350 ][ 350 ],a,b,p,n,flo[ 350 ][ 350 ],gt[ 350 ][ 350 ],ans,size[ 350 ],cnt[ 350 ],tag[ 350 ]; void dfs( int u, int dep, in
? ? 倍感自己傻逼 错的地方极其智障,一定不会犯了 打死不用vectorXD #include<bits/stdc++.h> using namespace std; int mp[350][350],a,b,p,n,flo[350][350],gt[350][350],ans,size[350],cnt[350],tag[350]; void dfs(int u,int dep,int fa) { cnt[u]=1; for(int i=1;i<=n;i++) if(mp[u][i]&&i!=fa) { flo[dep][++flo[dep][0]]=i; gt[u][++size[u]]=i; dfs(i,dep+1,u); cnt[u]+=cnt[i]; } } void lock(int u){tag[u]=1;for(int i=1;i<=size[u];i++)lock(gt[u][i]);} void unlock(int u){tag[u]=0;for(int i=1;i<=size[u];i++)unlock(gt[u][i]);} void dfs2(int ud,int now) { for(int i=1;i<=flo[ud][0];i++) { if(tag[flo[ud][i]])continue; lock(flo[ud][i]); dfs2(ud+1,now-cnt[flo[ud][i]]); unlock(flo[ud][i]); } ans=min(ans,now); } int main() { cin>>n>>p; ans=n; while(p--){cin>>a>>b;mp[a][b]=mp[b][a]=1;} dfs(1,2,0); dfs2(2,n); cout<<ans; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |