题目大意：给出 n 个错误，再给出 m 个补丁，对于每个补丁而言，设 b1,b2,f1,f2 分别为四个集合：当且仅当 b1 所表示的错误全部存在且 b2 所表示的错误没有任何一个存在时才可以使用该补丁，使用该补丁会花费 t 的时间，使用该补丁后会：修复掉 f1 中的所有错误，重新制造出 f2 中的错误，问修复掉 n 个错误的最短时间
题目分析：因为 n 只有 20，所以考虑状压，然后就是类似于 dp 一样的最短路转移了，一提到最短路转移到的 dp ，spfa 肯定是一个不错的选择
不过问题就是，为什么 spfa 还活着。。而且为什么这个题目会被归到网络流24题中。。
代码：
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=110;int n,m;char s[N];bool vis[(1<<20)+100];int d[(1<<20)+100];struct Node
{int t,b1,b2,f1,f2;
}p[N];void spfa()
{memset(d,inf,sizeof(d));int st=(1<<n)-1;queue<int>q;q.push(st);d[st]=0;vis[st]=true;while(q.size()){int u=q.front();q.pop();vis[u]=false;for(int i=1;i<=m;i++)if((u|p[i].b1)==u&&(u&p[i].b2)==0){int v=(u&p[i].f1)|p[i].f2;if(d[v]>d[u]+p[i].t){d[v]=d[u]+p[i].t;if(!vis[v]){q.push(v);vis[v]=true;}}}}
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d",&p[i].t);scanf("%s",s);for(int j=0;j<n;j++){if(s[j]=='+')p[i].b1|=(1<<j);if(s[j]=='-')p[i].b2|=(1<<j);}scanf("%s",s);for(int j=0;j<n;j++){if(s[j]!='-')p[i].f1|=(1<<j);if(s[j]=='+')p[i].f2|=(1<<j);}}spfa();if(d[0]==inf)puts("0");elseprintf("%d\n",d[0]);return 0;
}
