牛客练习赛114 G-图上异或难题(线性基)

题目要求把点涂成白和黑两种颜色，如果一条边左右两端是不同的颜色的话，结果就异或这跳边的权值，求结果最大是多少

把边的贡献转换成点的贡献

我们只考虑白色点的情况下，如果一个点A是白色，就把结果异或上这一个点A周围的所有边，

如果在该点周围还有一个白色点B的话，那么我们同样把结果异或上这个点B的所有边

因为我们知道两个点是有线段相连，而且两个点都异或上该点周围的所有边了

所以两个点相邻的线段就被去掉了

其他点同理

这时候我们就可以把这个问题转换成一个线性基的问题

已知所以点的贡献是该点异或上周围所有边

求从n个点中选出一部分点染成白色的最大异或和

const int inf = 0x3f3f3f3f3f3f3f3f, N = 2e5 + 5, mod = 1e9 + 7;
vector<int>q[N];
int a[N];
signed main()
{ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);int T;cin >> T;while (T--){int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {q[i].clear(); a[i] = 0;}while (m--){int u, v, w;cin >> u >> v >> w;q[u].push_back(w);q[v].push_back(w);}for (int i = 1; i <= n; i++) {for (auto w : q[i]){a[i] ^= w;}}int k = 1;for (int i = 32; i >= 0; i--){for (int j = k; j <= n; j++) {if (a[j] >> i & 1) {swap(a[j], a[k]);break;}}if (!(a[k] >> i & 1)) continue;for (int j = 1; j <= n; j++) {if (j != k && (a[j] >> i & 1))a[j] ^= a[k];}k++;if (k == n + 1) break;}int res = 0;for (int i = 1; i <= k; i++) {res ^= a[i];}cout << res << "\n";}
}