洛谷題目鏈接：軟件補(bǔ)丁問題

題目背景

none!

題目描述

T 公司發(fā)現(xiàn)其研制的一個軟件中有 n 個錯誤，隨即為該軟件發(fā)放了一批共 m 個補(bǔ)丁程序。每一個補(bǔ)丁程序都有其特定的適用環(huán)境，某個補(bǔ)丁只有在軟件中包含某些錯誤而同時又不包含另一些錯誤時才可以使用。一個補(bǔ)丁在排除某些錯誤的同時，往往會加入另一些錯誤。

換句話說，對于每一個補(bǔ)丁 i，都有 2 個與之相應(yīng)的錯誤集合 B1[i]和 B2[i]，使得僅當(dāng)軟件包含 B1[i]中的所有錯誤，而不包含 B2[i]中的任何錯誤時，才可以使用補(bǔ)丁 i。補(bǔ)丁 i 將修復(fù)軟件中的某些錯誤 F1[i]，而同時加入另一些錯誤 F2[i]。另外，每個補(bǔ)丁都耗費(fèi)一定的時間。

試設(shè)計一個算法，利用 T 公司提供的 m 個補(bǔ)丁程序?qū)⒃浖迯?fù)成一個沒有錯誤的軟件，并使修復(fù)后的軟件耗時最少。對于給定的 n 個錯誤和 m 個補(bǔ)丁程序，找到總耗時最少的軟件修復(fù)方案。

輸入輸出格式

輸入格式：

?

第 1 行有 2 個正整數(shù) n 和 m，n 表示錯誤總數(shù)，m表示補(bǔ)丁總數(shù)，1<=n<=20, 1<=m<=100。

接下來 m 行給出了 m 個補(bǔ)丁的信息。每行包括一個正整數(shù)，表示運(yùn)行補(bǔ)丁程序 i 所需時間，以及 2 個長度為 n 的字符串，中間用一個空格符隔開。

第 1 個字符串中，如果第 k 個字符 bk 為“+”，則表示第 k 個錯誤屬于 B1[i]，若為“-”，則表示第 k 個錯誤屬于 B21[i]，若為“0”，則第 k 個錯誤既不屬于 B1[i]也不屬于 B2[i]，即軟件中是否包含第 k 個錯誤并不影響補(bǔ)丁 i 的可用性。

第 2 個字符串中，如果第 k 個字符 bk為“-”，則表示第 k 個錯誤屬于 F1[i]，若為“+”，則表示第 k 個錯誤屬于 F2[i]，若為“0”，則第 k 個錯誤既不屬于 F1[i]也不屬于 F2[i]，即軟件中是否包含第 k 個錯誤不會因使用補(bǔ)丁i 而改變。

?

輸出格式：

?

程序運(yùn)行結(jié)束時，將總耗時數(shù)輸出。如果問題無解，則輸出 0。

?

輸入輸出樣例

輸入樣例#1：?
3 3 1 000 00- 1 00- 0-+ 2 0-- -++ 輸出樣例#1：?
8

說明

none!

?

?

如果讓我給這道題取個名字，我會叫它位運(yùn)算的藝術(shù)（因為這道題用了一些很有意思的位運(yùn)算）。

這道題雖然是網(wǎng)絡(luò)流24題之一，但是我并沒有想到怎么用網(wǎng)絡(luò)流來做。這里分享一波最短路的做法。

首先簡單說一下題意：題目給出一個軟件(???)，并且它有n個錯誤，而現(xiàn)在有m個補(bǔ)丁來修復(fù)這些問題，第i個補(bǔ)丁的使用條件是軟件包含 B1[i]中的所有錯誤，而不包含 B2[i]中的任何錯誤，得到的效果是修復(fù)軟件中的某些錯誤 F1[i]，而同時加入另一些錯誤 F2[i]，以及代價是t[i]，現(xiàn)在要求最小的代價使所有的錯誤都被修復(fù)。

那么看到這個錯誤總量N<=20，就可以采用一些比較好確定哪些位置有問題，比如狀壓。那么n個錯誤也就可以用n位來表示，若該位為1，則該位有錯誤，若為0，則沒有。那么我們在存下判斷是否可以使用補(bǔ)丁的b1，b2時也可以用狀壓的思想。那么我們就可以把狀態(tài)看成點(diǎn)，耗費(fèi)某個補(bǔ)丁的時間看成邊，這個問題就轉(zhuǎn)換成了從(1<<n)-1（有n個錯誤的狀態(tài)）到0（所有狀態(tài)都被消除）的最短路。那么這個問題就簡單了，我們只需要判斷從一個狀態(tài)能轉(zhuǎn)換到什么狀態(tài)，并且記錄下最短路徑。

然后剩下的就是一些神奇的位運(yùn)算操作了。

　　１．位邏輯運(yùn)算符：

　　　　&?（位 ? “與”） ?and (00001010 & 00000010 -> 00000010)

　　　　^??（位 ? “異或”）xor (00110010 ^ 11110001 -> 11000011)

　　　　|?? （位 ? ?“或”） ? or (00010001 | 11000101 -> 11010101)

　　　　~??（位 ? “取反”）(~10100100 -> 01011011)

　　２．移位運(yùn)算符：

　　　　<<（左移）(00001001 << 2 -> 00100100)

　　　　>>（右移）(11010010 >> 3 -> 00011010)//左移或右移溢出時會直接過濾掉

?利用這些操作，我們可以實現(xiàn)這道題的一些操作，推薦還是先自己想一下怎么實現(xiàn)，比較鍛煉自己的能力。

另外重點(diǎn)強(qiáng)調(diào)：位運(yùn)算的優(yōu)先級非常低，比判斷等于還要低！！！

下面看一下代碼注釋。

#include<bits/stdc++.h> using namespace std; const int M=100+5; const int N=22;int n, m; char s1[30], s2[30]; int dist[1<<N]; bool vis[1<<N]; void out(int);struct fix{int b1, b2, f1, f2, t; }a[M];int spfa(){memset(dist,127,sizeof(dist));queue <int> q; int s = (1<<n)-1 , inf = dist[0], nx;dist[s] = 0; vis[s] = 1; q.push(s);while(!q.empty()){//求最短路int x = q.front(); q.pop(); vis[x] = 0;for(int i=1;i<=m;i++){if(((~x)&a[i].b1) != 0) continue;if((x&a[i].b2) != 0) continue;//這兩個判斷與b1,b2的關(guān)系nx = (x | a[i].f2);nx = (nx & (~a[i].f1));//如果可以打該補(bǔ)丁，則得到新狀態(tài)nx，進(jìn)行松弛if(dist[nx] > dist[x] + a[i].t){dist[nx] = dist[x]+a[i].t;if(!vis[nx]) vis[nx] = 1 , q.push(nx);}}}return dist[0]==inf?0:dist[0]; }int main(){//freopen("data.in","r",stdin);int x; cin >> n >> m;for(int i=1;i<=m;i++){scanf("%d%s%s",&x,s1,s2);a[i].t = x;for(int j=0;j<n;j++){if(s1[j] == '+') a[i].b1 += 1<<n-j-1;//讀入并壓成二進(jìn)制if(s1[j] == '-') a[i].b2 += 1<<n-j-1;if(s2[j] == '+') a[i].f2 += 1<<n-j-1;if(s2[j] == '-') a[i].f1 += 1<<n-j-1;}}printf("%d\n",spfa());return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/BCOI/p/8612732.html

總結(jié)

以上是生活随笔為你收集整理的软件补丁问题（网络流24题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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