首页 > 代码库 > BZOJ 2466 中山市选2009 树 高斯消元+暴力
BZOJ 2466 中山市选2009 树 高斯消元+暴力
题目大意:树上拉灯游戏
高斯消元解异或方程组,对于全部的自由元暴力2^n枚举状态,代入计算
这做法真是一点也不优雅。。。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 110 using namespace std; int n,m; int f[M][M],is_free[M],tot; int ans[M],cnt; void Gauss_Elimination() { int i,j,k,l; //第i个方程 第j个变量 for(i=1,j=1;i<=n;i++,j++) { if(j==n+1) { for(j=i;j<=n;j++) if(f[j][n+1]==1) { puts("-1"); exit(0); } m=i-1; return ; } for(k=i;k<=n;k++) if(f[k][j]) break; if(k==n+1) { is_free[j]=++tot; i--; continue; } for(l=j;l<=n+1;l++) swap(f[i][l],f[k][l]); for(k=i+1;k<=n;k++) if(f[k][j]) for(l=j;l<=n+1;l++) f[k][l]^=f[i][l]; } m=n; } void Get_Ans() { int i,j,k; for(j=n+1,i=m;i;i--) { for(j--;j&&is_free[j];j--); ans[j]=f[i][n+1]; for(k=j+1;k<=n;k++) if(f[i][k]) ans[j]^=ans[k]; } } void Initialize() { memset(f,0,sizeof f); memset(is_free,0,sizeof is_free); ans[0]=0x3f3f3f3f; tot=0; } int main() { int i,j,x,y; while(cin>>n,n) { Initialize(); for(i=1;i<=n;i++) f[i][i]=1,f[i][n+1]=1; for(i=1;i<n;i++) { scanf("%d%d",&x,&y); f[x][y]=f[y][x]=1; } Gauss_Elimination(); for(i=0;i<1<<tot;i++) { for(j=1;j<=n;j++) if(is_free[j]) ans[j]=(i>>is_free[j]-1)&1; Get_Ans(); cnt=0; for(j=1;j<=n;j++) if(ans[j]) cnt++; ans[0]=min(ans[0],cnt); } cout<<ans[0]<<endl; } return 0; }
BZOJ 2466 中山市选2009 树 高斯消元+暴力
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。