luogu2761 软件补丁问题

状压最短路
#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

using namespace std;

struct Node{

    int bi1, bi2, fi1, fi2;

}nd[105];

int n, m, ww[105], cnt, dis[1050005];

bool vis[1050005];

char a[25], b[25];

queue<int> d;

void spfa(){

    memset(dis, 0x3f, sizeof(dis));

    int uu=(1<<n)-1;

    dis[uu] = 0;

    d.push(uu);

    vis[uu] = true;

    while(!d.empty()){

        int x=d.front();

        d.pop();

        vis[x] = false;

        for(int i=1; i<=m; i++)

            if((x&nd[i].bi1)==nd[i].bi1 && (x&nd[i].bi2)==0){

                int tmp=x;

                tmp &= ~(nd[i].fi1);

                tmp |= nd[i].fi2;

                if(dis[tmp]>dis[x]+ww[i]){

                    dis[tmp] = dis[x] + ww[i];

                    if(!vis[tmp]){

                        vis[tmp] = true;

                        d.push(tmp);

                    }

                }

            }

    }

}

int main(){

    cin>>n>>m;

    for(int i=1; i<=m; i++){

        scanf("%d", &ww[i]);

        scanf("%s %s", a, b);

        for(int j=0; j<n; j++){

            if(a[j]=='+')	nd[i].bi1 |= 1<<j;

            if(a[j]=='-')	nd[i].bi2 |= 1<<j;

        }

        for(int j=0; j<n; j++){

            if(b[j]=='-')	nd[i].fi1 |= 1<<j;

            if(b[j]=='+')	nd[i].fi2 |= 1<<j;

        }

    }

    spfa();

    if(dis[0]==0x3f3f3f3f)	cout<<"0"<<endl;

    else	cout<<dis[0]<<endl;

    return 0;

}
巴特西

luogu2761 软件补丁问题

最新文章

热门文章
