题解 P2962 【[USACO09NOV]灯Lights】

· · 题解

先挂个博客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;
}