如果一條邊可行，那么刪掉這條邊后，剩下的圖是二分圖且該邊的兩端點(diǎn)顏色相同。

那么可行的邊必然屬于所有奇環(huán)的交集，且不屬于任何偶環(huán)。

隨便取一棵生成樹，對于一條非樹邊，它形成了環(huán)：

若是偶環(huán)，則將環(huán)上的邊都標(biāo)記為不能選。

若是奇環(huán)，則將環(huán)上的邊經(jīng)過的奇環(huán)數(shù)都加一。

可以用樹鏈剖分維護(hù)前綴和做到$O(m\log n)$。

對于其它的環(huán)，都可以由以下三種情況得到：

1.一個(gè)奇環(huán)異或一個(gè)偶環(huán)得到一個(gè)新的奇環(huán)，公共部分一定經(jīng)過了偶環(huán)，即使不標(biāo)記也會被舍去。

2.一個(gè)奇環(huán)異或一個(gè)奇環(huán)得到一個(gè)新的偶環(huán)，新環(huán)上的邊一定不屬于所有奇環(huán)的交，即使不標(biāo)記也會被舍去。

3.一個(gè)偶環(huán)異或一個(gè)偶環(huán)得到一個(gè)新的偶環(huán)，公共部分一定經(jīng)過了偶環(huán)且被標(biāo)記過了，所以無需再次標(biāo)記。

因此只需要考慮所有兩兩之間異或可以表示出所有環(huán)的基環(huán)即可。

?

#include<cstdio> #define N 300010 int n,m,i,x,y,f[N],g[N],nxt[N<<1],v[N<<1],ed,son[N],size[N],d[N],dis[N],top[N],loc[N],dfn,s[2][N]; int e[N][2],need[N],ban[N],cnt,ans; int F(int x){return f[x]==x?x:f[x]=F(f[x]);} inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;v[++ed]=x;nxt[ed]=g[y];g[y]=ed; } void dfs(int x,int y){size[x]=1,d[x]=d[f[x]=y]+1,dis[x]=dis[y]+(x<=n);for(int i=g[x];i;i=nxt[i])if(v[i]!=y){dfs(v[i],x);size[x]+=size[v[i]];if(size[v[i]]>size[son[x]])son[x]=v[i];} } void dfs2(int x,int y){top[x]=y;loc[x]=++dfn;if(son[x])dfs2(son[x],y);for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]); } inline void modify(int x,int y,int p){for(;top[x]!=top[y];x=f[top[x]]){if(d[top[x]]<d[top[y]]){int z=x;x=y;y=z;}s[p][loc[top[x]]]++,s[p][loc[x]+1]--;}if(d[x]<d[y]){int z=x;x=y;y=z;}s[p][loc[y]]++,s[p][loc[x]+1]--; } inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} int main(){read(n),read(m);for(i=1;i<=n;i++)f[i]=i;for(i=1;i<=m;i++){read(x),read(y),e[i][0]=x,e[i][1]=y;if(F(x)!=F(y))f[f[x]]=f[y],add(x,i+n),add(y,i+n);else need[i]=1;}for(i=1;i<=n;i++)if(!d[i])dfs(i,0),dfs2(i,i);for(i=1;i<=m;i++)if(need[i]){x=e[i][0],y=e[i][1];if((dis[x]&1)^(dis[y]&1))ban[i]=1,modify(x,y,0);else modify(x,y,1),cnt++;}for(i=2;i<=dfn;i++)s[0][i]+=s[0][i-1],s[1][i]+=s[1][i-1];for(i=1;i<=m;i++)if(need[i]){if(!ban[i]&&cnt==1)ans++;}else{if(!s[0][loc[i+n]]&&s[1][loc[i+n]]==cnt)ans++;}return printf("%d",ans),0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/clrs97/p/4737869.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ4238 : 电压的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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