自动搬运

查看原文

来自洛谷，原作者为

	YoungLove **

搬运于2025-08-24 21:43:53，当前版本为作者最后更新于2017-11-23 20:57:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先挂个博客Youngsc欢迎来踩

高斯消元，对于一个灯我只有按或者不按两种状态，如果按也只会按一次，最终我们希望所有的灯的状态都为$1$，那么对于每一个灯$i$的状态就是与它相连的每一个灯包括它自己按或者不按的状态$d[i]$的异或和$$(a[1][i]*d[1])xor(a[2][i]*d[2])\cdots(a[n][i]*d[n])=1$$待求的元素就是$d[]$，就可以得到一个$n\*(n+1)$方程组，然后用高斯消元之后会得到一个上三角矩阵，但你可能会产生一些自由元，此时我们采用DFS的方法，消完元后的矩阵相当于重新定义了两个灯之间的关系以及每个灯要到达的状态，由于该矩阵是一个上三角矩阵，意味着此时你要做的就是让所有的灯都符合等号右边的状态，由于新的关系可以保证每一个灯都只会被他后边的灯所影响(注意在消元之后两个灯之间的新关系不一定是双向的)，因此我们从后往前搜，如果这个不是自由元那么我们就可以根据后边灯的状态来判断它按或者不按，如是自由元的话，我们就要枚举一下按或者不按，再分别搜索。

# include <bits/stdc++.h>
# define R register
# define db double
# define mi 1e-8

using namespace std;

int n,m,x,y,ans=10000,l[110];
int a[110][110];

template <typename T> inline void in(R T& a){
    R char c=getchar(); R T x=0,f=1;
    while(!isdigit(c)) {if(c == '-') f=-1; c=getchar();}
    while(isdigit(c)) x=(x<<1)+(x<<3)+c-'0',c=getchar();
    a=x*f;
}

template <typename T> inline T ab(R T& a){return a<0? -a:a;}

inline bool gauss(){//高斯消元
    R bool flagg=1;
    for(R int i=1; i<=n; ++i)
    {
        R int k=i;
        while(k<=n&&!a[k][i]) k++;
        if(k>n) {flagg=0; continue;}
        swap(a[i],a[k]);
        for(R int j=1; j<=n; ++j)
        {
            if(i==j||!a[j][i]) continue;
            for(R int k=i+1; k<=n+1; ++k) a[j][k]^=a[i][k];
            a[j][i] = 0;
        }
    }
    return flagg;
}

inline void dfs(R int x,R int num){
    // printf("%d ",x);
    if(num>=ans) return;//剪枝
    if(x == 0){ans = num; return;}
    if(a[x][x])//不是自由元
    {
        R bool v=a[x][n+1];
        for(R int i=x+1; i<=n; ++i) if(a[x][i]) v^=l[i];
        dfs(x-1,num+v);
    }
    else{
        dfs(x-1,num);
        l[x]=1;
        dfs(x-1,num+1);
        l[x]=0;
    }
}

int main(){
    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);
    in(n),in(m);
    for(R int i=1; i<=n; ++i) a[i][i] = a[i][n+1] = 1;
    for(R int i=1; i<=m; ++i) in(x),in(y),a[x][y] = a[y][x] = 1;
    if(gauss()){
        R int ans = 0;
        for(R int i=1; i<=n; ++i) ans += a[i][n+1];
        printf("%d",ans);
    }
    else dfs(n,0),printf("%d\n",ans);
    return 0;
}