題目大意：給出一張 n 個(gè)點(diǎn) m 條邊的無向連通圖，現(xiàn)在有某些點(diǎn)被標(biāo)記了，問能否通過刪除某個(gè)未被標(biāo)記的點(diǎn)，使得刪除該點(diǎn)后的數(shù)個(gè)互不相交的連通塊中，至少存在一個(gè)聯(lián)通塊中不含有被標(biāo)記的點(diǎn)
題目分析：首先不難看出，被刪掉的點(diǎn)一定是割點(diǎn)，所以我們可以直接用 tarjan 求出割點(diǎn)，然后點(diǎn)雙縮一下點(diǎn)，將整個(gè)圖縮成一棵樹，在樹上dp即可，dp 的話對(duì)于點(diǎn) u 而言，只需要檢查一下其所有子樹，以及其父節(jié)點(diǎn)上面的那棵子樹中，是否存在著不含有標(biāo)記點(diǎn)的子樹即可
代碼：
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;const int M=1e6+100;struct Egde
{int to,next;
}edge1[M],edge2[M];int head1[N],head2[N],low[N],dfn[N],c[N],Stack[N],new_id[N],dp[N],num,cnt,cnt1,cnt2,tot,root,top,n,m,b;bool cut[N],ban[N];vector<int>dcc[N];vector<int>ans;map<int,int>mp;void addedge1(int u,int v)
{edge1[cnt1].to=v;edge1[cnt1].next=head1[u];head1[u]=cnt1++;
}void addedge2(int u,int v)
{edge2[cnt2].to=v;edge2[cnt2].next=head2[u];head2[u]=cnt2++;
}void tarjan(int u)
{dfn[u]=low[u]=++num;Stack[++top]=u;if(u==root&&head1[u]==-1){dcc[++cnt].push_back(u);return;}int flag=0;for(int i=head1[u];i!=-1;i=edge1[i].next){int v=edge1[i].to;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]){flag++;if(u!=root||flag>1)cut[u]=true;cnt++;int x;do{x=Stack[top--];dcc[cnt].push_back(x);}while(x!=v);dcc[cnt].push_back(u);}}elselow[u]=min(low[u],dfn[v]);}
}void solve()
{for(int i=1;i<=n;i++)//找割點(diǎn)+縮點(diǎn) if(!dfn[i]){root=i;tarjan(i);}
}void build()//縮點(diǎn)+連邊
{solve();num=cnt;for(int i=1;i<=n;i++)if(cut[i]){new_id[i]=++num;mp[num]=i;}for(int i=1;i<=cnt;i++)for(int j=0;j<dcc[i].size();j++){int x=dcc[i][j];if(cut[x]){addedge2(i,new_id[x]);addedge2(new_id[x],i);}elsec[x]=i;}
}void dfs(int u,int fa)
{bool flag=false;for(int i=head2[u];i!=-1;i=edge2[i].next){int v=edge2[i].to;if(v==fa)continue;dfs(v,u);if(!dp[v])flag=true;dp[u]+=dp[v];}if(mp.count(u)&&!ban[mp[u]]&&(flag||dp[u]==b))ans.push_back(mp[u]);
}void init()
{for(int i=0;i<N;i++)dcc[i].clear();cnt=cnt2=cnt1=num=tot=top=0;memset(head2,-1,sizeof(head2));memset(head1,-1,sizeof(head1));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(cut,false,sizeof(cut));memset(c,0,sizeof(c));memset(Stack,0,sizeof(Stack));memset(new_id,0,sizeof(new_id));memset(dp,0,sizeof(dp));memset(ban,false,sizeof(ban));mp.clear();ans.clear();
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);init();scanf("%d%d%d",&n,&m,&b);while(m--){int u,v;scanf("%d%d",&u,&v);addedge1(u,v);addedge1(v,u);}build();for(int i=1;i<=b;i++){int x;scanf("%d",&x);ban[x]=true;if(cut[x])dp[new_id[x]]++;elsedp[c[x]]++;}dfs(1,-1);sort(ans.begin(),ans.end());printf("%d\n",ans.size());for(int num:ans)printf("%d ",num);return 0;
}
?
總結(jié)
以上是生活随笔 為你收集整理的中石油训练赛 - Plan B(点双缩点+树形dp) 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
