正題

題目鏈接:https://loj.ac/p/3130

---

題目大意

給出$n$個點(diǎn)$m$條邊的一張有權(quán)無向圖，你每次可以選擇一個邊集異或上一個值，要求最少次數(shù)使得所有簡單環(huán)異或和都為$0$。

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

---

解題思路

先找一棵生成樹，然后每條非樹邊都會產(chǎn)生一個簡單環(huán)，顯然這些簡單環(huán)合法了其他的也一定合法。

而肯定存在一種最優(yōu)的方案是只改非樹邊，因為如果該樹邊首先我們可以一次改一個集合所有必須改一條樹邊會對多個簡單環(huán)產(chǎn)生不同的影響，而如果我們異或的是$val$，那么我們能做到的只是讓某個簡單環(huán)異或上$val$（奇數(shù)條樹邊操作），或者不異或上$val$（偶數(shù)條樹邊操作），所以是和我們操作非樹邊能做到的是相同的。

那么問題就變?yōu)橐阎恍?shù)要異或多少，求最少操作次數(shù)了，我們用線性基求出最小的線性空間就好了。

時間復(fù)雜度：$O(n+m\log m)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define mp(x,y) make_pair(x,y) using namespace std; const int N=1e5+10; struct node{int to,next,w; }a[N<<1]; int n,m,tot,k,w[N],d[N],ls[N],v[N]; bool vis[N]; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;return; } void dfs(int x,int fa){vis[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;if(vis[y]){if(i&1)v[(i+1)/2]=w[x]^w[y]^a[i].w;}else{w[y]=w[x]^a[i].w;dfs(y,x);}}return; } void ins(int x){for(int i=29;i>=0;i--)if((x>>i)&1){if(d[i])x^=d[i];else {d[i]=x;k+=(x!=0);break;}}return; } int main() {scanf("%d%d",&n,&m);for(int i=1,x,y,w;i<=m;i++){scanf("%d%d%d",&x,&y,&w);addl(x,y,w);addl(y,x,w);}dfs(1,0);for(int i=1;i<=m;i++)ins(v[i]);printf("%d\n",k);for(int i=0;i<=29;i++)if(d[i]){int cnt=0;for(int j=1;j<=m;j++)cnt+=((v[j]>>i)&1);printf("%d %d ",d[i],cnt);for(int j=1;j<=m;j++)if((v[j]>>i)&1)printf("%d ",j);putchar('\n');}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Loj#3130-「COCI 2018.12」Praktični【线性基】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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