题解：CF1846G Rudolf and CodeVid-23

Solution CF1846G

Idea

注意到

n\le 10

，这启示我们状压，毕竟最多只有

2^{10}=1024

种状态。

然后最短路转移就枚举初始状态

u

，然后就考虑吃第

i

种药。第

i

种药会治好

x_i

（其中

x_i

是一个二进制数，这一位是

1

代表可以治好）的病，产生

y_i

（同

x_i

）的副作用。

那么问题来了：末状态

v

是什么呢？

设

t

的反状态为：

t

二进制下所有为

1

的位变为

0

，

0

的位变为

1

。所以

t

的反状态

u=(2^n-1) \oplus t

。

那么

x_i

的反状态

xx_i

就代表吃下药

i

之后无法治好的病。那么原先得的病，和无法治好的病取个并，就可以得到吃下药

i

产生副作用之前可以得到的病了。

至于副作用，与刚才的副作用之前的值或一下就行。这个理解起来很容易：只要这一个药可以产生，或者之前就得了，就会患。

然后枚举初状态

u

，枚举药，按照上面算出末状态

v

，然后跑最短路就行。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int get(string s){
    int res=0,t=1;
    for(int i=0;i<s.length();i++){
        res=res+t*(s[i]=='1');
        t<<=1;
    }
    return res;
}
int n,m,dis[1<<N],vis[1<<N];
string tmp;
struct node{
    int x,y,t;
}a[1005];
void solve(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<(1<<n);i++){
        dis[i]=0x3f3f3f3f;
        vis[i]=0;
    }
    cin>>tmp;
    dis[get(tmp)]=0;
    for(int i=1;i<=m;i++){
        cin>>a[i].t;
        cin>>tmp;
        a[i].x=get(tmp);
        cin>>tmp;
        a[i].y=get(tmp);
    }
    while(1){
        int u=-1;
        for(int i=0;i<(1<<n);i++){
            if(vis[i]||dis[i]==0x3f3f3f3f)continue;
            if(u==-1||dis[i]<dis[u]){
                u=i;
            }
        }
        if(u==-1)break;
        vis[u]=1;
        for(int i=1;i<=m;i++){
            int w=a[i].t;
            int v=(u&(((1<<n)-1)^a[i].x))|a[i].y;
            dis[v]=min(dis[v],dis[u]+w);
        }  
    }
    cout<<(dis[0]==0x3f3f3f3f ? -1 : dis[0])<<endl;
}
int main(){
    int T;cin>>T;
    while(T--)solve();
}

题解：CF1846G Rudolf and CodeVid-23

文章操作

Solution CF1846G

Idea

Code

相关推荐

评论

题解：CF1846G Rudolf and CodeVid-23