★★☆ 输入文件:lights.in
输出文件:lights.out
简单对比
时间限制:1 s 内存限制:128 MB
【问题描述】
贝希和她的闺密们在她们的牛棚中玩游戏。但是天不从人愿,突然,牛棚的电源跳闸了,所有的灯都被关闭了。贝希是一个很胆小的女生,在伸手不见拇指的无尽的黑暗中,她感到惊恐,痛苦与绝望。她希望您能够帮帮她,把所有的灯都给重新开起来!她才能继续快乐地跟她的闺密们继续玩游戏!
牛棚中一共有N(1 <= N <= 35)盏灯,编号为1到N。这些灯被置于一个非常复杂的网络之中。有M(1 <= M <= 595)条很神奇的无向边,每条边连接两盏灯。
每盏灯上面都带有一个开关。当按下某一盏灯的开关的时候,这盏灯本身,还有所有有边连向这盏灯的灯的状态都会被改变。状态改变指的是:当一盏灯是开着的时候,这盏灯被关掉;当一盏灯是关着的时候,这盏灯被打开。
问最少要按下多少个开关,才能把所有的灯都给重新打开。
数据保证至少有一种按开关的方案,使得所有的灯都被重新打开。
题目名称:lights
输入格式:
*第一行:两个空格隔开的整数:N和M。
*第二到第M+1行:每一行有两个由空格隔开的整数,表示两盏灯被一条无向边连接在一起。
没有一条边会出现两次。
样例输入(文件 lights.in):
5 6
1 2
1 3
4 2
3 4
2 5
5 3
输入细节:
一共有五盏灯。灯1、灯4和灯5都连接着灯2和灯3。
输出格式:
第一行:一个单独的整数,表示要把所有的灯都打开时,最少需要按下的开关的数目。
样例输出(文件 lights.out):
3
输出细节:
按下在灯1、灯4和灯5上面的开关。
题解:
和poj 1681几乎一样,dfs的不懂的看这。。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
int N,M,ANS;
int a[][];
void gauss(){
for(int i=;i<=N;i++){
int tmp=i;
while(tmp<=N&&a[tmp][i]==) tmp++;
if(tmp>N) continue;
if(tmp!=i){
for(int j=;j<=N+;j++) swap(a[i][j],a[tmp][j]);
}
for(int j=;j<=N;j++){
if(j!=i&&a[j][i]==){
for(int k=;k<=N+;k++) a[j][k]^=a[i][k];
}
}
}
}
int s[],cnt;
void dfs(int x){
if(cnt>=ANS) return;
if(x==){
ANS=min(ANS,cnt);
return;
}
if(a[x][x]){
int num=a[x][N+];
for(int i=x+;i<=N;i++)
if(a[x][i])
num=num^s[i];
s[x]=num;
if(num==) cnt++;
dfs(x-);
if(num==) cnt--;
}
if(!a[x][x]){
s[x]=;
dfs(x-); s[x]=; cnt++;
dfs(x-); cnt--;
}
}
int main(){
//freopen("lights.in","r",stdin);
//freopen("lights.out","w",stdout);
scanf("%d%d",&N,&M);
for(int i=;i<=N;i++) a[i][i]=;
for(int i=,u,v;i<=M;i++){
scanf("%d%d",&u,&v);
a[u][v]=a[v][u]=;
}
for(int i=;i<=N;i++) a[i][N+]=;
gauss();
ANS=<<;
dfs(N);
printf("%d",ANS);
return ;
}