P3921 小学数学题 题解

· · 题解

1. 题意解释

有 n 个妖精在一个湖边，每次可以使不超过 r 只妖精达到湖的另一边。在每一时刻，有 m_1 条限制，即妖精 a_i 必须与妖精 b_i 在湖的同一侧，且有另外 m_2 条限制，即妖精 a 不能同时与妖精 b 和妖精 c 分居湖的两侧。求最短的运输次数即在此前提下的方案数。

2. 思路

看到 1\le n\le15 立马想到状压。

所谓状压，即用一个 n 位二进制数表示当前状态，第 i 位为 0 代表妖精 i 还未过湖，否则已经过湖。

于是我们可以先预处理出所有的合法状态。

然后考虑如何转移。

由于转移必须是把一个妖精的状态改变，所以直接异或上一就可以了。

我们也可以预处理出所有合法的转移状态。

然后我们跑一个 BFS 最短路计数就可以了，具体解释见代码注释。

3. 代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m1,m2,r,can[1<<15],a,b,c,trans[1<<15],cnt=1,dis[1<<15],ans[1<<15];
queue<int>q;
int lowbit(int x){
    return x&-x;
}
int popcount(int x){
    int ret=0;
    while(x){
        ret++;
        x-=lowbit(x);
    }
    return ret;
}//求出一个二进制数里 1 的个数
void bfs(){
    memset(dis,0x3f,sizeof dis);
    q.push(0);
    dis[0]=0;
    ans[0]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=1;i<=cnt;i++){
            int v=(u^trans[i]);
            if(can[v]!=-1){
                if(dis[v]>dis[u]+1){
                    dis[v]=dis[u]+1;
                    ans[v]=ans[u];
                    q.push(v);
                }
                else if(dis[v]==dis[u]+1){
                    ans[v]+=ans[u];
                }
            }
        }
    }
}//BFS 求最短路及方案，和 P1144 最短路计数类似，其实就是把枚举每一条边换成了枚举转移方案
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m1>>m2>>r;
    for(int i=1;i<=m1;i++){
        cin>>a>>b;
        for(int j=0;j<(1<<n);j++){
            if((((j>>(a-1))&1)^((j>>(b-1))&1))==1){//这里 (j>>(a-1))&1) 是取出第 a 位，然后两位异或判断是否在同一边
                can[j]=-1;
            }
        }
    }
    for(int i=1;i<=m2;i++){
        cin>>a>>b>>c;
        for(int j=0;j<(1<<n);j++){
            if((((j>>(a-1))&1)^((j>>(b-1))&1))==1&&(((j>>(a-1))&1)^((j>>(c-1))&1))==1){//和上面的差不多，分别判断 a 与 b，a 与 c 的关系
                can[j]=-1;
            }
        }
    }
    for(int i=0;i<(1<<n);i++){//预处理转移方案
        if(popcount(i)<=r){
            trans[cnt]=i;
            cnt++;
        }
    }
    cnt--;
    bfs();
    cout<<((dis[(1<<n)-1]!=0x3f3f3f3f3f3f3f3f)?dis[(1<<n)-1]:-1)<<" "<<ans[(1<<n)-1];//记得判断是否有解
    return 0;
}