UVA 658 状态压缩+隐式图+优先队列dijstla

不可多得的好题目啊,我看了别人题解才做出来的,这种题目一看就会做的实在是大神啊,而且我看别人博客都看了好久才明白。。。还是对状态压缩不是很熟练,理解几个位运算用了好久时间。有些题目自己看着别人的题解做出来完全不是一个味,毕竟别人给你提供了思路,比如这道题,刚看题目,怎么就能转移到是用最短路搜索呢。。其次,好多注意事项这些自己想出来才真正是锻炼思维。否则总是踩着别人的脚印在行走

还有就是不得不说一说UVA上的题目,又长又难懂。。。实在是弄得我好烦。

说说这个题目,能够发现是个隐式图是第一个难点,然后怎么进行搜索就是关键了,状态压缩确实是个好东西,通过二进制来表示当前bug是否被修复,1 为bug,0为已修复,因此,初始状态就是n个1,因为补丁有诸多限制,有的需要某个bug已经被修复了才能运行该补丁,有些需要某些bug还在,每个bug分别用两个变量来分别记录需要哪些bug被修复,以及哪些bug需要存在,此外,补丁可以修补某个bug的同时又可能会产生新的bug,同样用两个变量来记录bug的消失和产生。

用到的pair和优先队列,第一次用,还需要继续熟悉。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
struct node
{
    int value;
    int bp,bm,tp,tm;
} patch[110];
int vis[1<<20];
bool flag;
typedef pair<int , int> pill;
struct cmp
{
    bool operator()(const pill a,const pill b){
     return a.first>b.first;
    }
};

priority_queue<pill,vector<pill>,cmp> q;
int nbug,npatch,vmin;
void init()
{
    flag=0;
    while (!q.empty())
      q.pop();
    memset(vis,0,sizeof vis);
    for (int i=0;i<=npatch;i++)
    {
        patch[i].bp=patch[i].bm=patch[i].tp=patch[i].tm=0;
    }
}
void dijstla()
{
    q.push(make_pair(0,(1<<nbug)-1));
    while (!q.empty())
    {
        pill u=q.top();
        q.pop();
        //printf("%x\n",u.second);
        if (u.second==0)
        {
            flag=1;
            vmin=u.first;
            return;
        }
        if (vis[u.second]) continue;
        vis[u.second]=1;
        for (int i=0;i<npatch;i++)
        {
            int t=u.second;
            if (((t&patch[i].bp)==patch[i].bp) && (((~t)&patch[i].bm)==patch[i].bm))
            {
               t|=patch[i].tp;
               t&=(~patch[i].tm);
            }
            q.push(make_pair(u.first+patch[i].value,t));
        }
    }
}
int main()
{
    int i,j;
    char c1[25],c2[25];
    int cnt=0;
    while (scanf("%d%d",&nbug,&npatch))
    {
        if (!nbug && !npatch) break;
        init();
        for (i=0;i<npatch;i++)
        {
            scanf("%d%s%s",&patch[i].value,c1,c2);
            for (j=0;j<nbug;j++)
            {
                if (c1[j]==+) patch[i].bp=patch[i].bp|(1<<j);
                if (c1[j]==-) patch[i].bm=patch[i].bm|(1<<j);
                if (c2[j]==+) patch[i].tp=patch[i].tp|(1<<j);
                if (c2[j]==-) patch[i].tm=patch[i].tm|(1<<j);
            }
        }
        dijstla();
        printf("Product %d\n",++cnt);
        if (!flag)
        {
            puts("Bugs cannot be fixed.");
        }
        else
        {
            printf("Fastest sequence takes %d seconds.\n",vmin);
        }
        putchar(\n);
    }
    return 0;
}

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。