本文共 745 字，大约阅读时间需要 2 分钟。

题目大意： 一开始有一个含有 $n$ 个错误的软件，还有 $m$ 个补丁，第 $i$ 个补丁只有当软件包含 $B1[i]$ 集合中的所有错误以及不包含 $B2[i]$ 集合中的任何错误才能使用，使用后会将 $F1[i]$ 集合中的错误消除，并且会加入 $F2[i]$ 集合中的错误。问将软件修改到无错误最少要用几个补丁。

题解

不知道为啥在网络流 $24$ 题里，这应该就是个最短路呀qwq

做法很简单，由于 $n$ 很小，于是可以把 $2^n-1$ 个状态都列出来，然后从 $2^n-1$ 开始跑SPFA，每次看能打哪个补丁，然后转移即可。

代码如下：

#include 
   
    #include 
    
     #define maxn 1100000#define ll long longint n,m,t[maxn];char s[maxn];int B1[maxn],B2[maxn],F1[maxn],F2[maxn];int q[maxn],st=1,ed=2;ll f[maxn];bool v[maxn];void spfa(){
   	memset(f,63,sizeof(f));	q[st]=(1<
     
      ((1<
      
       f[x]+t[i])			{
   				f[y]=f[x]+t[i];				if(!v[y])v[q[ed++]=y]=true,ed=ed>((1<
       
        1e18?0:f[0]);}
       
      
     
    
   

转载地址：http://gcnib.baihongyu.com/