洛谷P2761 软件补丁问题（状压；最短路）

题目介绍题目描述输入格式输出格式输入输出样例 题解思路细节 代码

题目介绍

链接: 传送门.

题目描述

T 公司发现其研制的一个软件中有 n 个错误，随即为该软件发放了一批共 m 个补丁程序。每一个补丁程序都有其特定的适用环境，某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时，往往会加入另一些错误。 换句话说，对于每一个补丁 i，都有 2 个与之相应的错误集合 B1[i]和 B2[i]，使得仅当软件包含 B1[i]中的所有错误，而不包含 B2[i]中的任何错误时，才可以使用补丁 i。补丁 i 将修复软件中的某些错误 F1[i]，而同时加入另一些错误 F2[i]。另外，每个补丁都耗费一定的时间。 试设计一个算法，利用 T 公司提供的 m 个补丁程序将原软件修复成一个没有错误的软件，并使修复后的软件耗时最少。对于给定的 n 个错误和 m 个补丁程序，找到总耗时最少的软件修复方案。

输入格式

第 1 行有 2 个正整数 n 和 m，n 表示错误总数，m表示补丁总数，1<=n<=20, 1<=m<=100。 接下来 m 行给出了 m 个补丁的信息。每行包括一个正整数，表示运行补丁程序 i 所需时间，以及 2 个长度为 n 的字符串，中间用一个空格符隔开。 第 1 个字符串中，如果第 k 个字符 bk 为“+”，则表示第 k 个错误属于 B1[i]，若为“-”，则表示第 k 个错误属于 B21[i]，若为“0”，则第 k 个错误既不属于 B1[i]也不属于 B2[i]，即软件中是否包含第 k 个错误并不影响补丁 i 的可用性。 第 2 个字符串中，如果第 k 个字符 bk为“-”，则表示第 k 个错误属于 F1[i]，若为“+”，则表示第 k 个错误属于 F2[i]，若为“0”，则第 k 个错误既不属于 F1[i]也不属于 F2[i]，即软件中是否包含第 k 个错误不会因使用补丁i 而改变。

输出格式

程序运行结束时，将总耗时数输出。如果问题无解，则输出 0。

输入输出样例

输入#1 3 3 1 000 00- 1 00- 0-+ 2 0-- -++

输出#1 8

题解

思路

原本在网络流标签题目中找到这题，做了一会发现如果建网络的话，状态分配与边必然无法存储。于是改为最短路的思路。

首先，由题目数据n<=20以及题目以类似01串表示软件错误状态，可以想到状态压缩。接着状态转移的边如何实现？题目中给出了补丁的接受条件和转移状态。而由于其接受和转移条件不是点对点、而是集合对集合，若选择加边则会Re。因此选择保留补丁，作为一种特殊的边，每次对当前结点遍历补丁，判断是否能够使用该补丁、以及使用后状态。

细节

对每个补丁，对其修补的软件需要满足的状态设为target1(对应位为1),对其修补的软件不允许有错误的状态为target2(禁止位为1)；对其消去的bug的二进制表示设为repair，对其增加的bug的表示为add。 当前结点为now，若满足 （now&target1 == target1），且 （now&target2 == 0）则对应要求bug位为1、禁止bug位为0. 其下一状态为nxt = now&(~repair)|add。表示消去位若为1则消去、增加位若为0则对应增加1。 对每个结点使用补丁判断其相邻边，从而构建图。 跑最短路算法即可。

代码

#include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; /* 对小范围n和m可用网络流； 稍大数据适合状压dp */ typedef long long ll; const int maxn=2e6+5; const int INF=0x3f3f3f3f; const int inf=0x3f; typedef struct Node{ int target1,target2,repair,add,cost; }Patch; Patch patch[105]; int S,T; int N,M; int dis[maxn]; bool vis[maxn]; void Dijkstra(){ memset(dis,inf,sizeof(dis)); memset(vis,false,sizeof(vis)); priority_queue<pair<int,int> > que; dis[S]=0; que.push(make_pair(0,S)); int now,nxt; while(!que.empty()){ now=que.top().second; que.pop(); if(vis[now] ) continue; vis[now]=true; for(int i=1;i<=M;i++){ if((now&patch[i].target1)==patch[i].target1&& (now&patch[i].target2)==0){ // 满足修补(松弛)条件 // 消去patch[i].repair中的1，并或上patch[i].add nxt=(now&(~patch[i].repair))|patch[i].add; if(dis[nxt]>dis[now]+patch[i].cost){ dis[nxt]=dis[now]+patch[i].cost; que.push(make_pair(-dis[nxt], nxt) ); } } } } if(dis[T]==INF) printf("0\n"); else printf("%d\n",dis[T]); } int main(){ scanf("%d%d",&N,&M); S=(1<<N)-1; T=0; char s1[21],s2[maxn]; for(int i=1;i<=M;i++){ // patch转换为边 scanf("%d %s %s",&patch[i].cost,&s1,&s2); for(int j=0;j<N;j++){ if(s1[j]=='+') patch[i].target1 +=1<<j; else if(s1[j]=='-') patch[i].target2 +=1<<j; if(s2[j]=='+') patch[i].add +=1<<j; else if(s2[j]=='-') patch[i].repair +=1<<j; } } Dijkstra(); }

最后： (1)这题加边的方式属实巧妙，值得学习。 (2)需要注意思维定势，不能老用一种思路做题。