还是高斯消元解异或方程组
如果这个你不会，请看这里
现在假定你已经会这个东西了
那么我们就可以构造模型了
首先有一个很显然的结论：一个开关至多只需要按一次！（因为按两次等于不按，按三次等于按一次....）
我们设一盏灯开的状态为1，关的状态为0，那么我们的目标就是把所有灯的状态都改成1
那么能影响到一盏灯的因素就是所有关联他的开关以及他本身
那么我们设每个开关的状态为$x_i$，与这盏灯有关的开关集合为S，那么一个灯最后的要求就是
$sum_{i∈S}x_i==1$（这里的$sum$表示异或和）
那么就是异或方程组了，用高斯消元解之即可
但是会有自由元的问题，所以我们要用dfs枚举每个自由元的状态，使得取得1的x数量最小，注意剪枝即可
然后就结束了
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <vector> using namespace std; int a[45][45]; int n,m; vector <int> v[45]; void Gauss() { for(int i=1;i<=n;i++) { int temp=i; while(!a[temp][i]&&temp<=n)temp++; if(temp>n)continue; if(temp!=i)for(int j=i;j<=n+1;j++)swap(a[i][j],a[temp][j]); for(int j=1;j<=n;j++)if(a[j][i]&&j!=i)for(int k=i;k<=n+1;k++)a[j][k]^=a[i][k]; } } int ans=0x3f3f3f3f; void dfs(int dep,int sum) { if(sum>=ans)return; if(!dep){ans=sum;return;} if(a[dep][dep])dfs(dep-1,sum+a[dep][n+1]); else { if(a[dep][n+1])return; dfs(dep-1,sum); for(int j=dep-1;j>=1;j--)a[j][n+1]^=a[j][dep]; dfs(dep-1,sum+1); for(int j=dep-1;j>=1;j--)a[j][n+1]^=a[j][dep]; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); v[x].push_back(y),v[y].push_back(x); } for(int i=1;i<=n;i++) { for(int j=0;j<v[i].size();j++)a[i][v[i][j]]=1; a[i][i]=a[i][n+1]=1; } Gauss(); dfs(n,0); printf("%d ",ans); return 0; }