正題

題目鏈接:https://www.luogu.com.cn/problem/P4494

---

題目大意

給出$n$個(gè)點(diǎn)$m$條邊的一張無向圖，節(jié)點(diǎn)有$0/1$，每條邊可以選擇是否取反兩邊的點(diǎn)。

開始求將所有節(jié)點(diǎn)變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">$0$的方案，然后對于每個(gè)點(diǎn)詢問刪去這個(gè)點(diǎn)之后的方案

$1\le T\le 5,1\le n,m\le 10^5$

---

解題思路

圖的比較麻煩，先考慮樹上的，那么每條邊取不取反取決于它連接的子節(jié)點(diǎn)的黑白，但是根節(jié)點(diǎn)卻無法這么調(diào)整。所以如果黑色個(gè)數(shù)為奇數(shù)個(gè)那么方案為$0$，否則方案為$1$。

然后考慮一張連通圖，考慮對于圖中的一個(gè)生成樹來說，無論非生成樹上的邊是否取反，都可以用這棵生成樹調(diào)整回來，也就是如果黑色為奇數(shù)個(gè)方案為$0$，否則方案為$2^{m?n+1}$。

因?yàn)樵瓐D不一定連通，設(shè)連通塊個(gè)數(shù)為$k$，那么第一問答案就是$2^{m?n+k}$（每個(gè)連通塊的黑色個(gè)數(shù)為奇數(shù)個(gè)）。

然后第二問，其實(shí)就是去掉這條邊之后會(huì)分割一個(gè)連通塊以影響答案。

建立廣義圓方樹，統(tǒng)計(jì)每個(gè)點(diǎn)刪去后會(huì)多產(chǎn)生的連通塊數(shù)量以及是否有分割出來的連通塊的黑色個(gè)數(shù)為奇數(shù)。

順帶一提的是需要特判如果有兩個(gè)或者以上的連通塊黑色為奇數(shù)個(gè)，那么全都無解，否則只有可能刪除掉黑色奇數(shù)連通塊里的點(diǎn)。

時(shí)間復(fù)雜度$O(Tn)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<vector> #define ll long long using namespace std; const ll N=2e5+10,P=1e9+7; ll Z,n,m,dfc,sum,cnt,st[N],deg[N]; ll dfn[N],low[N],pw[N],siz[N]; bool tag[N],nok[N],v[N]; stack<ll> s;char t[N]; vector<ll>G[N],T[N]; void tarjan(ll x){dfn[x]=low[x]=++dfc;sum+=(t[x]=='1');s.push(x);st[++st[0]]=x;for(ll i=0;i<G[x].size();i++){ll y=G[x][i];if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);if(low[y]==dfn[x]){ll k;++cnt;do{k=s.top();s.pop();deg[k]--;T[cnt].push_back(k);T[k].push_back(cnt);}while(k!=y);T[cnt].push_back(x);T[x].push_back(cnt);deg[x]--;}}else low[x]=min(low[x],dfn[y]);}return; } void dfs(ll x){v[x]=1;st[++st[0]]=x;siz[x]=(x<=n)&(t[x]=='1');for(ll i=0;i<T[x].size();i++){ll y=T[x][i];if(v[y])continue;dfs(y);siz[x]+=siz[y];if(siz[y]&1)nok[x]=1;}return; } signed main() {scanf("%lld",&Z);pw[0]=1;for(ll i=1;i<N;i++)pw[i]=pw[i-1]*2%P;while(Z--){dfc=0;memset(deg,0,sizeof(deg));memset(nok,0,sizeof(nok));memset(tag,0,sizeof(tag));memset(dfn,0,sizeof(dfn));memset(v,0,sizeof(v));while(!s.empty())s.pop();scanf("%lld%lld",&n,&m);for(ll i=1;i<=2*n;i++)T[i].clear(),G[i].clear();for(ll i=1;i<=m;i++){ll x,y;scanf("%lld%lld",&x,&y);G[x].push_back(y);deg[x]++;G[y].push_back(x);deg[y]++;}scanf("%s",t+1);cnt=n;ll one=0,k=0;for(ll i=1;i<=n;i++){if(dfn[i])continue;st[0]=sum=0;tarjan(i);k++;if(sum&1){for(ll j=1;j<=st[0];j++)tag[st[j]]=1;one++;}}if(one>1){for(ll i=0;i<=n;i++)printf("0 ");putchar('\n');continue;}else if(one)printf("0 ");else printf("%lld ",pw[m-n+k]);for(ll i=1;i<=n;i++){if(v[i])continue;st[0]=0;dfs(i);for(ll j=1;j<=st[0];j++)if((siz[i]-siz[st[j]])&1)nok[st[j]]=1;}for(ll i=1;i<=n;i++)if(nok[i]||(one&&!tag[i]))printf("0 ");else printf("%lld ",pw[m-n+k-deg[i]]);putchar('\n');}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P4494-[HAOI2018]反色游戏【圆方树】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。