link

contest link

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;
}

标签: 构造

添加新评论