e760 - 658 - It's not a Bug, it's a Feature!
題目描述
題目描述了修復 bug 的問題。有 n 個 bug 和 m 個補丁。每個補丁需要一定的時間來安裝，並且可能依賴於其他 bug 的存在或不存在，同時安裝補丁也可能引起或修復其他 bug。目標是找到修復所有 bug 的最少時間。
解題思路
這題可以建模為一個圖論問題。每個 bug 的狀態（存在或不存在）可以用一個位元表示，因此總共有 2^n 個狀態。圖的節點代表 bug 的狀態，邊代表安裝一個補丁的操作。邊的權重是安裝補丁所需的時間。
使用 Dijkstra 演算法來尋找從所有 bug 都存在（狀態為 2^n - 1）到所有 bug 都消失（狀態為 0）的最短路徑。
cnt 函數檢查是否可以安裝某個補丁，即檢查補丁的依賴條件是否滿足。
tran 函數模擬安裝補丁後 bug 狀態的變化。
djsk 函數實現 Dijkstra 演算法。
複雜度分析
- 時間複雜度: O(2^n * m)。Dijkstra 演算法的時間複雜度通常是 O(E log V)，其中 V 是節點數，E 是邊數。在這裡，V = 2^n，E = 2^n * m。
- 空間複雜度: O(2^n)。需要一個大小為 2^n 的陣列
dis來儲存每個狀態的最短距離。
程式碼
#include <bits/stdc++.h>
using namespace std;
int dis[1<<20],n,m,ca;
bool has[1<<20];
struct bd{
int tm;
string nd,gt;
};
bd a[105];
bool cnt(int id,int v){
for(int i=0;i<n;++i){
int k=v%2;
if((a[id].nd[i]=='+'&&k==0)||(a[id].nd[i]=='-'&&k==1))return 0;
v/=2;
}
return 1;
}
int tran(int id,int v){
string rt;
int rtv=0;
for(int i=0;i<n;++i){
int k=v%2;
if(a[id].gt[i]=='+')k=1;
else if(a[id].gt[i]=='-')k=0;
rt+=(k+'0');
v/=2;
}
for(int i=n-1;i>=0;--i){
rtv*=2;
rtv+=rt[i]-'0';
}
return rtv;
}
void djsk(int bst){
queue <pair <int,int>> pq;//dis v
pq.push({0,bst});
dis[bst]=0;
while(!pq.empty()){
int ft=pq.front().first,sec=pq.front().second;
pq.pop();
for(int i=0;i<m;++i){
if(cnt(i,sec)){
int tt=tran(i,sec);
if(dis[tt]>dis[sec]+a[i].tm){
dis[tt]=dis[sec]+a[i].tm;
pq.push({dis[tt],tt});
}
}
}
}
return;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n >> m){
if(n+m==0)break;
memset(has,0,sizeof(has));
for(int i=0;i<(1<<n);++i)dis[i]=1e9;
for(int i=0;i<m;++i)cin >> a[i].tm >> a[i].nd >> a[i].gt;
djsk((1<<n)-1);
cout << "Product " << ++ca << "\n";
(dis[0]>=1e9)?cout << "Bugs cannot be fixed.\n":cout << "Fastest sequence takes " << dis[0] << " seconds.\n";
cout << "\n";
}
}