【bzoj2466】【中山市选】【树】【高斯消元+dfs】
发布日期:2021-11-16 15:38:45
浏览次数:11
分类:技术文章
本文共 1514 字,大约阅读时间需要 5 分钟。
Description
图论中的树为一个无环的无向图。给定一棵树,每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了,那么该节点的灯会从熄灭变为点亮(当按之前是熄灭的),或者从点亮到熄灭(当按之前是点亮的)。并且该节点的直接邻居也发生同样的变化。
开始的时候,所有的指示灯都是熄灭的。请编程计算最少要按多少次按钮,才能让所有节点的指示灯变为点亮状态。Input
输入文件有多组数据。
输入第一行包含一个整数n,表示树的节点数目。每个节点的编号从1到n。 输入接下来的n – 1行,每一行包含两个整数x,y,表示节点x和y之间有一条无向边。 当输入n为0时,表示输入结束。Output
对于每组数据,输出最少要按多少次按钮,才能让所有节点的指示灯变为点亮状态。每一组数据独占一行。
Sample Input
3 1 2 1 3 0
Sample Output
1
HINT
对于100%的数据,满足1 <= n <=100。
题解:
首先可以发现一个灯最多按一次,多按没有意义。
所以对于每个点xa我们可以写出一个方程。map[x][1]表示两点是否有边。
map[a][1]*x1 xor map[a][2]*x2 xor map[a][3]*x3 ....=1;
然后有n个点我们就可以列出n个方程
这样高斯消元会产生一些自由元。
暴搜自由元即可。
代码:
#include#include #include #define N 200int f[N][N],mn(99999),ans[N],x,y,n,m,tot;using namespace std;void gauss(){ for (int i=1;i<=n;i++){ int j=i; while (j<=n&&!f[j][i]) j++; if (j>n) continue; for (int k=1;k<=n+1;k++) swap(f[i][k],f[j][k]); for (int j=i+1;j<=n;j++) if (f[j][i]) for (int k=1;k<=n+1;k++) f[j][k]^=f[i][k]; }}void dfs(int x){ if (tot>=mn) return; if (!x){mn=min(tot,mn);return;} if (f[x][x]){ int t=f[x][n+1]; for (int i=x+1;i<=n;i++) if (f[x][i]) t^=ans[i]; ans[x]=t;if(t) tot++; dfs(x-1);if(t) tot--; } else{ ans[x]=0;dfs(x-1); ans[x]=1;tot++;dfs(x-1);tot--; }}int main(){ while(1){ scanf("%d",&n);mn=99999;tot=0; if (!n) break;memset(f,0,sizeof(f)); for (int i=1;i<=n;i++) f[i][i]=f[i][n+1]=1; for (int i=1;i<=n-1;i++){ scanf("%d%d",&x,&y); f[x][y]=1;f[y][x]=1; } gauss();dfs(n); printf("%d\n",mn); }}
转载地址:https://blog.csdn.net/sunshinezff/article/details/51123163 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年03月04日 07时18分56秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
matlab结果怎么输入excel,MATLAB怎么在保存结果的EXCEL里面添加内容?
2019-04-21
php 输入二维数组,php中二维数组如何使用
2019-04-21
php.ini配置文件内容,php.ini配置文件信息分享
2019-04-21
php architecture x86,PHP Architecture
2019-04-21
php 合并切片的文件,webuploder+PHP实现大文件断点(切片)续传
2019-04-21
php 选择日期限制多少人代码,如何使用element-ui 限制日期选择
2019-04-21
oracle中rman坏块,Oracle基础教程之通过RMAN修复坏块
2019-04-21
oracle数据库优化11g,ORACLE 11G SQL 调优
2019-04-21
oracle 查找所有有数据的表,Oracle 查找数据库中有记录的表
2019-04-21
Oracle syskm,Python cx_Oracle.SYSDBA属性代码示例
2019-04-21
oracle的osw是什么,Tools:OSW工具-Oracle的OS watcher
2019-04-21
Linux系统如何植入脚本,【1分钟系列教程】Linux系统Shell脚本编写思路与过程
2019-04-21
linux 虚拟机 网络打印机,Fedora 17中实现虚拟机共享host虚拟打印机
2019-04-21
linux获取本进程参数,linux如何用pid获取进程参数?
2019-04-21
linux挂载文件系统上的时间,linux文件系统的挂载和自动挂载
2019-04-21
python中zip什么意思_python中zip是什么函数
2019-04-21
android bp文件_[Android]恋恋APK登录协议分析
2019-04-21