正題

題目鏈接:http://www.ybtoj.com.cn/contest/118/problem/3

---

解題思路

給出$n$個點(diǎn)，$m$次動態(tài)插入一條無向邊詢問：割掉一些邊使得圖中至少兩點(diǎn)不連通，并且割掉的邊異或和最大。

詢問之間相互獨(dú)立

$1\le n\le 500,1\le m\le 1000$

邊權(quán)以二進(jìn)制形式給出，長度不超過$1000$

---

解題思路

要求分隔兩個點(diǎn)，看起來很麻煩，其實(shí)有個結(jié)論。先定義$w_i$表示連接$i$的所有邊的異或和，如果選出了一個點(diǎn)集$U$和外面的所有點(diǎn)都隔絕，那么割就是點(diǎn)集$U$中所有點(diǎn)的$w_i$值異或和。

其實(shí)挺顯然的，因?yàn)槿绻麅蓚€點(diǎn)集中的點(diǎn)$x,y$之間的邊被異或了兩次就抵消掉了。

那么現(xiàn)在問題就變?yōu)榱嗣看涡薷膬蓚€數(shù)，求最大異或和。

然后就是帶修線性基的裸題了，有兩種方法

在線做法是先刪除再插入，就是開一個0行儲存所有的沒有成功插入線性基的元素，然后還要對于每個元素維護(hù)一個它插入的時候異或了哪些元素。

每次你刪除一個元素$x$的時候，假設(shè)集合$S$中儲存了所有插入的時候異或了$x$的元素（包括$x$本身），那么我們找出一個最小的$y\in S$（異或后），讓所有$S$中的其他元素異或上$y$之后再將$yxorc$插入（$c$表示你要讓$x$異或的值）
此時就相當(dāng)于你將之前插入$x$時本應(yīng)該異或的數(shù)變成了異或$xxorc$的，選出最小的$y$防止對后面的元素產(chǎn)生影響，然后修改后讓$y$代替$x$成為新的主元插入。
加一個$bitset$優(yōu)化，時間復(fù)雜度$O(\frac{m(n+L)L}{w})$

離線的做法是線段樹分治，一個$x$的取值會被分為不同的時間段，每次將$x$的固定的時間段插入到線段樹的對應(yīng)區(qū)間，然后分治下去的時候維護(hù)一個撤銷線性基就好了。

時間復(fù)雜度$O(\frac{m{L}^2\log m}{w})$（也許？）

這里寫的是在線的做法

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<bitset> using namespace std; const int N=1010; bitset<N>w[N],v[N],c,ans; int n,m,p[N];char s[N]; void Insert(int x){for(int i=N-1;i>=0;i--)if(w[x][i]){if(p[i])w[x]^=w[p[i]],v[x]^=v[p[i]];else{p[i]=x;return;}}return; } void Change(int x){int pos=0;for(int i=1;i<=n;i++)if(v[i][x]&&!w[i].any()){pos=i;break;}if(!pos)for(int i=0;i<N;i++)if(p[i]&&v[p[i]][x]){pos=p[i];p[i]=0;break;}for(int i=1;i<=n;i++)if(v[i][x]&&i!=pos)w[i]^=w[pos],v[i]^=v[pos];w[pos]^=c;Insert(pos);return; } int main() {freopen("cut.in","r",stdin);freopen("cut.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)v[i][i]=1;for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);scanf("%s",s);int l=strlen(s);c.reset();for(int j=0;j<l;j++)c[j]=s[l-j-1]-'0';Change(x);Change(y);bool flag=0;ans.reset();for(int i=N-1;i>=0;i--){if(p[i]&&!ans[i])ans^=w[p[i]];if(ans[i])flag=1;if(flag)printf("%d",ans[i]?1:0);}if(!flag)puts("0");else putchar('\n');}return 0; }

總結(jié)

以上是生活随笔為你收集整理的YbtOJ#883-最大的割【带修线性基】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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