UOJ

分析

结论：如果有解，那么步数必然 $\leq m+1$。

证明：首先操作 $2$ 可以合并，所以只需要进行至多一次；其次，我们随便造一个生成森林，那么每条非树边就相当于一个简单环，从而操作 $1$ 的次数不会超过非树边数。所以总操作数至多为 $m-n+2\leq m+1$。

于是我们只需要判是否有解即可。

那么我们相当于要选若干个简单环异或 $1$，使得所有 $1$ 边变成 $0$，从而有解的充要条件是与每个节点相连的 $1$ 边数都是偶数。

于是我们可以列出一个异或方程组（变量是每个点有没有进行 $2$ 操作），直接高斯消元即可判断是否有解。时间复杂度 $\mathcal{O}(T\frac{n^3}{\omega})$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300+10;

int n,m;
bitset<N> A[N];

bool Gauss(int n) {
    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=1;j<=n;++j)
            if (i!=j&&A[j][i]) A[j]^=A[i];
    }
    for (int i=1;i<=n;++i)
        if (A[i].count()==1&&A[i][n+1]) return 0;
    return 1;
}

int main() {
    int T=read();
    while (T--) {
        n=read(),m=read();
        for (int i=1;i<=n;++i) A[i].reset();
        for (int i=1;i<=m;++i) {
            int u=read(),v=read(),w=read();
            A[u].flip(u),A[u].set(v),A[v].set(u),A[v].flip(v);
            if (w) A[u].flip(n+1),A[v].flip(n+1);
        }
        puts(Gauss(n)?"yes":"no");
    }
    return 0;
}