題目鏈接：點(diǎn)擊查看

題目大意：給出 n 個(gè)錯(cuò)誤，再給出 m 個(gè)補(bǔ)丁，對(duì)于每個(gè)補(bǔ)丁而言，設(shè) b1,b2,f1,f2 分別為四個(gè)集合：當(dāng)且僅當(dāng) b1 所表示的錯(cuò)誤全部存在且 b2 所表示的錯(cuò)誤沒(méi)有任何一個(gè)存在時(shí)才可以使用該補(bǔ)丁，使用該補(bǔ)丁會(huì)花費(fèi) t 的時(shí)間，使用該補(bǔ)丁后會(huì)：修復(fù)掉 f1 中的所有錯(cuò)誤，重新制造出 f2 中的錯(cuò)誤，問(wèn)修復(fù)掉 n 個(gè)錯(cuò)誤的最短時(shí)間

題目分析：因?yàn)?n 只有 20，所以考慮狀壓，然后就是類似于 dp 一樣的最短路轉(zhuǎn)移了，一提到最短路轉(zhuǎn)移到的 dp ，spfa 肯定是一個(gè)不錯(cuò)的選擇

不過(guò)問(wèn)題就是，為什么 spfa 還活著。。而且為什么這個(gè)題目會(huì)被歸到網(wǎng)絡(luò)流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; }

?

總結(jié)

以上是生活随笔為你收集整理的洛谷 - P2761 软件补丁问题(spfa+状压)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。