题解 P2962 【[USACO09NOV]Lights G】

· · 题解

P2962 [USACO09NOV]Lights G

题解：

双向搜索，已知 n 最大为 35 ，可以先通过对前面的 n/2 进行搜索，之后再对后 n/2 进行搜索，在搜索的过程中可对之前的每个状态进行匹配并输出最小值，这就是结果。

在实际编写的过程中

  1. 每个开关不能被重复使用。
  2. 需要用二进制来进行表示哪个状态使用过，哪个没有使用过。
  3. 最后是匹配是使用二进制 ^ 匹配前 n/2 的状态。

代码

#include <map>
#include <queue>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 600;
map<ll,int>mm[2];
vector<int>v[40];
int n,m;
inline ll exchar(ll ch,int x){
    if((ch>>x)&1)return ch-((ll)1<<x);
    return ch+((ll)1<<x);
}
inline int slove(){
    mm[0].clear();
    mm[1].clear();
    queue<pair<ll,ll> >q;
    ll s=0,e=((ll)1<<n)-1;
    q.push({s,0});mm[0][s]=0;
    while(!q.empty()){
        pair<ll,ll>p=q.front();
        q.pop();
        int k=mm[0][p.first];
        for(int i=0;i<n/2;++i){
            if((p.second>>i)&1)continue;
            pair<ll,ll>pp=p;
            pp.second+=((ll)1<<i);
            pp.first=exchar(pp.first,i);
            for(int j=0;j<v[i].size();++j){
                pp.first=exchar(pp.first,v[i][j]);
            }
            if(mm[0].count(pp.first)==0){
                mm[0][pp.first]=k+1;
                q.push(pp);
            }
        }
    }
    q.push({s,0});mm[1][s]=0;
    while(!q.empty()){
        pair<ll,ll>p=q.front();
        q.pop();
        int k=mm[1][p.first];
        for(int i=n/2;i<n;++i){
            if((p.second>>i)&1)continue;
            pair<ll,ll>pp=p;
            pp.second+=((ll)1<<i);
            pp.first=exchar(pp.first,i);
            for(int j=0;j<v[i].size();++j){
                pp.first=exchar(pp.first,v[i][j]);
            }
            if(mm[0].count(pp.first^e)){
                return mm[0][pp.first^e]+k+1;
            }
            if(mm[1].count(pp.first)==0){
                mm[1][pp.first]=k+1;
                q.push(pp);
            }
        }
    }
    return -1;
}
int main(){
    int x,y;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i){
        scanf("%d%d",&x,&y);
        --x;--y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    printf("%d\n",slove());
    return 0;
}