UOJ513 「UR#19」清扫银河
sblk写不对高斯消元
记不可通行的边边权为1,可通行的为0
考虑操作2相当于选择一些点，按顺序翻转和它相连的点。
所以只用做一次。
考虑只做操作1。
结论：可以只用操作1达到目标当且仅当每个点相邻的边权和是偶数。
证明：
必要性：对于一个环，翻转它不会影响环上点出边边权和的奇偶性（每个点都有两条相邻边被翻转）如果一个点边权和为奇数，则一定无法得到0。
充分性：只考虑1边，对于每个联通块跑欧拉回路，欧拉回路可以拆成一些环的和，翻转这些环。
考虑进行操作2之后要满足条件。
设第\(i\)个点被翻转的次数(0/1)为\(a_i\)，出边条数为\(s_i\)，出边边权和为\(w_i\)，出边到达点集合\(t_i\)。
则每个点满足方程\(a_is_i+w_i+\sum_{j\in t_i}a_j \equiv 0\pmod 2\)，高消求解即可。
代码：
vector<pii> to[305];
vector<int> xto[305];
int dfn[305],low[305],col[305],c,clk,stk[305],tp,s[305],vi[305],xcol[305],ok,can=1;
void dfs(int x,int f){
dfn[x]=low[x]=++clk;
stk[++tp]=x;
for(auto i:to[x])if(i.x!=f){
if(!dfn[i.x]){dfs(i.x,x);chkmin(low[x],low[i.x]);}
else if(!col[i.x])chkmin(low[x],low[i.x]);
}
if(dfn[x]==low[x]){
stk[tp+1]=-1;
++c;
while(stk[tp+1]!=x){
col[stk[tp]]=c;
--tp;
}
}
}
void dfsc(int x,int c){
xcol[x]=c;
for(auto i:xto[x])if(!~xcol[i])dfsc(i,c^1);
else if(xcol[i]==c)can=0;
}
bitset<305> a[305];
signed main(){
#ifdef QAQAutoMaton
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
#endif
int t,n,m,u,v,w;
read(t);
for(;t;--t){
read(n,m);
for(int i=1;i<=n;++i)to[i].clear();
for(int i=1;i<=n+1;++i)a[i].reset();
for(int i=1;i<=m;++i){
read(u,v,w);
a[u].flip(v);
a[v].flip(u);
a[u].flip(u);
a[v].flip(v);
if(w){
a[u].flip(n+1);
a[v].flip(n+1);
}
}
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[i],a[j]);break;}
}
}
for(int j=i+1;j<=n;++j)if(a[j][i])a[j]^=a[i];
}
bool ok=1;
for(int i=n;i;--i){
if(a[i][n+1] && a[i].count()==1){ok=0;break;}
for(int j=i-1;~j;--j){
if(a[j][i])a[j]^=a[i];
}
}
write(ok?"yes\n":"no\n");
}
return 0;
}