題意 ：

• 給n個點，m條邊，每條邊的邊權為w，是其連邊兩點的異或和，求出滿足題意的圖的最小點權和，如果不存在這樣的圖則輸出-1

思路 ：

• 異或的傳遞性質 ：有$a\oplus b=x,b\oplus c=y$，則$a\oplus c=x\oplus y$；推論 ：有$a_1\oplus a_2=w_1.a_2\oplus a_3=w_2,...$，則$a_1\oplus a_n=w_1\oplus w_2\oplus ...\oplus w_{n?1}$
• 異或的轉換性質 ：有$a\oplus b=c$，則$a\oplus c=b$
• 結合以上兩個性質 ：有$a_n=a_1\oplus w_1\oplus w_2\oplus ...\oplus w_{n?1}$，也就是每一塊連通區域內的其他任意點的點權與基點的點權的dfs關系
• 考慮本題，根據題意建圖，考慮每一塊連通區域，若合法，則只需對其中任意一點確定權值，則能確定連通塊中每一點的權值，并且任選其中一個點為該連通塊的基點，能確定該連通塊內任何一點與基點的異或和
• 因此，我們可以從1開始對所有未經過的點dfs，dfs過程中若某點已經被訪問過且無法擁有唯一確定點權（成環了），則輸出-1，且退出遍歷，否則在dfs過程中建立以本次dfs基點為中心的菊花圖，邊權為基點與目標點連邊的異或和
• 對每個建的新連通塊，基點的每一位都可以枚舉0和1兩種情況，取更小的（dfs時我們假設基點是000…0，如果某一位上這個連通區域內1的個數大于0的個數，基點的這一位就放1，因為原先異或性質導致一條邊的兩個端點同一位肯定是同時變化的），統計當前連通區域點權和時，已經確定連通塊基點點權為x，當前該點在基點為全0時取的是f[v]，考慮某一位，x現在仍是0，該點如果原先是0，現在也是0，該點如果原先是1，現在也是1；x現在如果是1，該點如果原先是0，現在應是1，該點如果原先是1，現在是0，所以累加答案是$f[v]\oplus x$

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <unordered_set> #include <math.h> #define endl '\n' #define fi first #define se second #define pb push_backusing namespace std; using ll = long long;typedef pair<int, int> PII;const int N = 1e5 + 10;int n, m; bool flag = true; vector<PII> g[N]; vector<int> res[N]; int f[N]; bool st[N];void dfs(int u, int lt) {st[u] = true;for (auto pii : g[u]){int v = pii.fi, w = pii.se;if (st[v]){if (f[v] != (f[u] ^ w)){flag = false;return ;}}else{f[v] = (f[u] ^ w);res[lt].pb(v);dfs(v, lt);}} }ll add(int lt) {int x = 0;for (int i = 0; i < 30; i ++ ){int cnt = 0;for (auto u : res[lt])if (f[u] >> i & 1) cnt ++ ;if (cnt > res[lt].size() / 2) x += (1 << i);}ll ans = x;for (auto u : res[lt]) ans += x ^ f[u];return ans; }int main() {cin.tie(nullptr) -> sync_with_stdio(false);int n, m; cin >> n >> m;for (int i = 0, u, v, w; i < m; i ++ ){cin >> u >> v >> w;g[u].pb({v, w}); g[v].pb({u, w});}ll ans = 0;for (int i = 1; i <= n; i ++ ){if (!st[i] && flag){dfs(i, i);ans += add(i);}}cout << (flag ? ans : -1) << endl;return 0; }

總結

以上是生活随笔為你收集整理的Bitwise Exclusive-OR Sequence 异或，dfs，菊花图（2021.11.沈阳）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。