【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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【bzoj3171】【TJOI2013】【循环格】【费用流】
下一篇:【bzoj3993】【SDOI2015】【二分法+最大流】

发表评论

最新留言

表示我来过!
[***.240.166.169]2024年03月04日 07时18分56秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

matlab结果怎么输入excel,MATLAB怎么在保存结果的EXCEL里面添加内容? 2019-04-21
matlab 获取拟合系数,matlab离散型数据拟合方程,求系数,哪个大神能说说方法... 2019-04-21
php 输入二维数组,php中二维数组如何使用 2019-04-21
php.ini配置文件内容,php.ini配置文件信息分享 2019-04-21
不修改php.ini 如何扩展,BAE基础版、专业版、BCH安装php扩展(无需修改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
appium python_python爬虫23|手机,上来自己动了这就是Appium Python的厉害之处 2019-04-21
python中zip什么意思_python中zip是什么函数 2019-04-21
android bp文件_[Android]恋恋APK登录协议分析 2019-04-21