題目鏈接

http://uoj.ac/contest/51/problem/513

題解

好題。
考慮簡化操作：
對于第二種操作，其實就可以等價于若干次單點操作，每次標記一個點，把和這個點相鄰的邊全部反轉。即有用的操作只有 \(n\) 種。
對于第一種操作，眾所周知一個無向圖中所有的環都可以由若干個非樹邊覆蓋的環異或得到。即有用的操作只有 \((m-n+1)\) 種。
這樣我們可以得到一個異或方程組，變量數和方程數都為 \((m+1)\). 這也證明了為什么只要有解就能在 \((m+1)\) 次操作內出解。
時間復雜度 \(O(\frac{m^3}{\omega})\)，期望得分 \(70\) 分。
考慮優化，通過歐拉回路不難證明一個子圖可以用第一種操作消去當且僅當子圖內每個點度都是偶數。
于是問題就變成了用第二種操作使得每個點度均為偶數。變量數量和方程數量都為 \(n\) 個。
時間復雜度 \(O(\frac{n^3}{\omega})\).

代碼

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define x first #define y second #define iter iterator #define riter reversed_iterator #define y1 Lorem_ipsum_dolor using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int mxN = 300; bitset<mxN+3> a[mxN+3]; int n,m,en;bool gauss() {for(int i=1; i<=n; i++){if(!a[i][i]){for(int j=i+1; j<=n; j++) if(a[j][i]) {swap(a[j],a[i]);}if(!a[i][i]) {continue;}}for(int j=i+1; j<=n; j++){if(a[j][i]) {a[j] ^= a[i];}}}for(int i=n; i>=1; i--){int tmp = a[i][n+1];for(int j=i+1; j<=n; j++) {tmp ^= (a[j][0]&a[i][j]);}if(!a[i][i]&&tmp) {return false;}a[i][0] = tmp;}return true; }int main() {int T = read(); while(T--){n = read(),m = read();for(int i=1; i<=m; i++){int u = read(),v = read(),w = read();a[u][u].flip(),a[v][v].flip(),a[u][v].flip(),a[v][u].flip();if(w) {a[u][n+1].flip(),a[v][n+1].flip();}}bool ans = gauss();if(ans) puts("yes"); else puts("no");for(int i=1; i<=n; i++) a[i].reset();}return 0; }

總結

以上是生活随笔為你收集整理的UOJ #513 [UR #19]清扫银河 (图论、线性基)的全部內容，希望文章能夠幫你解決所遇到的問題。

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