题解

102 条题解

  • 0
    @ 2006-01-22 17:27:00

    宽搜,用hash判重。

    hash可以将当前节点每个错误的情况看做一个01序列,则这个序列就是一个二进制数,

    然后就好办了~~~~~~~~~

    注意:第一次搜到的可行解并不一定是最优解。

  • -1
    @ 2016-11-01 22:51:42

    #include <cstdio>
    #include <cstring>
    #include <queue>
    #define add(a,k) a|=(1<<k)

    int n,m;
    int b1[150]={0},b2[150]={0},f1[150]={0},f2[150]={0};
    int time[110];

    int ans=999999999;

    int dist[32888];
    int inque[32888]={0};
    std::queue<int> q;

    void spfa(int u){
    for(int i=0;i<32888;i++)
    dist[i]=99999999;
    q.push(u),inque[u]=1;
    dist[u]=0;
    int t;
    while(!q.empty()){
    t=q.front();
    q.pop(),inque[t]=0;
    for(int i=1;i<=m;i++){
    int p=t;
    if((p&b1[i])==b1[i]&&(p&b2[i])==0){
    p|=f1[i],p&=(~f2[i]);
    if(dist[t]+time[i]<dist[p]){
    dist[p]=dist[t]+time[i];
    if(!inque[p]){
    q.push(p);
    inque[p]=1;
    }
    }
    }

    }

    }

    }

    int main(){
    freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
    scanf("%d",&time[i]);
    char c;
    for(int j=0;j<n;j++){
    scanf(" %c",&c);
    if(c=='+')
    add(b1[i],j);
    if(c=='-')
    add(b2[i],j);
    }
    for(int j=0;j<n;j++){
    scanf(" %c",&c);
    if(c=='+')
    add(f1[i],j);
    if(c=='-')
    add(f2[i],j);
    }

    }

    int begin=(1<<n)-1;
    spfa(begin);
    if(dist[0]==99999999)
    printf("0");
    else
    printf("%d",dist[0]);
    return 0;
    }

信息

ID
1019
难度
5
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
1604
已通过
511
通过率
32%
被复制
11
上传者