洛谷 P2962 [USACO09NOV]灯Lights

2021年09月15日 阅读数:2
这篇文章主要向大家介绍洛谷 P2962 [USACO09NOV]灯Lights,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目描述

Bessie and the cows were playing games in the barn, but the power was reset and the lights were all turned off. Help the cows get all the lights back on so they can resume their games.html

The N (1 <= N <= 35) lights conveniently numbered 1..N and their switches are arranged in a complex network with M (1 <= M <= 595) clever connection between pairs of lights (see below).ios

Each light has a switch that, when toggled, causes that light -- and all of the lights that are connected to it -- to change their states (from on to off, or off to on).网络

Find the minimum number of switches that need to be toggled in order to turn all the lights back on.ide

It's guaranteed that there is at least one way to toggle the switches so all lights are back on.spa

贝希和她的闺密们在她们的牛棚中玩游戏。可是天不从人愿,忽然,牛棚的电源跳闸了,全部的灯都被关闭了。贝希是一个很胆小的女生,在伸手不见拇指的无尽的黑暗中,她感到惊恐,痛苦与绝望。她但愿您可以帮帮她,把全部的灯都给从新开起来!她才能继续快乐地跟她的闺密们继续玩游戏! 牛棚中一共有N(1 <= N <= 35)盏灯,编号为1到N。这些灯被置于一个很是複杂的网络之中。有M(1 <= M <= 595)条很神奇的无向边,每条边链接两盏灯。 每盏灯上面都带有一个开关。当按下某一盏灯的开关的时候,这盏灯自己,还有全部有边连向这盏灯的灯的状态都会被改变。状态改变指的是:当一盏灯是开著的时候,这盏灯被关掉;当一盏灯是关著的时候,这盏灯被打开。 问最少要按下多少个开关,才能把全部的灯都给从新打开。 数据保证至少有一种按开关的方案,使得全部的灯都被从新打开。htm

输入输出格式

输入格式:

 

  • Line 1: Two space-separated integers: N and M.游戏

  • Lines 2..M+1: Each line contains two space-separated integers representing two lights that are connected. No pair will be repeated.

 

输出格式:

 

  • Line 1: A single integer representing the minimum number of switches that need to be flipped in order to turn on all the lights.

 

输入输出样例

输入样例#1:
5 6 
1 2 
1 3 
4 2 
3 4 
2 5 
5 3 
输出样例#1:
3 

说明

There are 5 lights. Lights 1, 4, and 5 are each connected to both lights 2 and 3.ip

Toggle the switches on lights 1, 4, and 5.get

思路:meet in the middlestring

蒟蒻实在不会HZWER大神

#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
map<long long,int>mp;
int n,m;
int mid,flag,minn=0x7f7f7f7f;
long long ed,qwq[40],mmp[40];
void dfs(int x,long long now,int step){
    if(x==mid+1){
        if(now==ed)
            minn=min(step,minn);
        if(!flag){
            int tmp=mp[now];
            if(!tmp||tmp>step)
                mp[now]=step;
        }
        else{
            int tmp=mp[ed-now];
            if(!tmp)    return ;
            minn=min(tmp+step,minn);
        }
        return ;
    }
    dfs(x+1,now,step);
    dfs(x+1,now^qwq[x],step+1);
}
int main(){
    mmp[1]=1;
    for(int i=2;i<=40;i++)
        mmp[i]=mmp[i-1]<<1;
    scanf("%d%d",&n,&m);
    ed=mmp[n+1]-1;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        qwq[x]+=mmp[y];
        qwq[y]+=mmp[x];
    }
    for(int i=1;i<=n;i++)
        qwq[i]+=mmp[i];
    mid=n/2;
    dfs(1,0,0);
    flag=1;
    mid=n;
    dfs(n/2+1,0,0);
    cout<<minn;
}

 

细雨斜风做晓寒。淡烟疏柳媚晴滩。入淮清洛渐漫漫。 雪沫乳花浮午盏,蓼茸蒿笋试春盘。人间有味是清欢。