首页 > 代码库 > 【网络流24题】 No.12 软件补丁问题（最小转移代价 最短路）

【网络流24题】 No.12 软件补丁问题（最小转移代价 最短路）

2024-08-18 23:15:38   217人阅读

【题意】

　　T 公司发现其研制的一个软件中有 n 个错误， 随即为该软件发放了一批共 m 个补丁程
序。 每一个补丁程序都有其特定的适用环境， 某个补丁只有在软件中包含某些错误而同时又
不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时， 往往会加入另一些错误。
换句话说， 对于每一个补丁 i， 都有 2 个与之相应的错误集合 B1[i]和 B2[i]，使得仅当软件
包含 B1[i]中的所有错误， 而不包含 B2[i]中的任何错误时， 才可以使用补丁 i。 补丁 i 将修复
软件中的某些错误 F1[i]， 而同时加入另一些错误 F2[i]。 另外， 每个补丁都耗费一定的时间。
试设计一个算法， 利用 T 公司提供的 m 个补丁程序将原软件修复成一个没有错误的软
件， 并使修复后的软件耗时最少。

输入文件示例
input.txt
3 3
1 000 00-
1 00- 0-+
2 0-- -++

输出文件示例
output.txt
8

 

【分析】

　　sm网络流24题，怎么什么题都有。

　　明明就是一道最短路，就spfa就好了。。。

　　最小转移代价，但是没什么约束，所以用不着流，直接费用跑过。。

 

技术分享 
 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cmath>
 8 #include<map>
 9 using namespace std;
10 #define Maxm 110
11 #define Maxn 1100000
12 #define INF 0xfffffff
13 
14 int w[Maxm],b1[Maxm],b2[Maxm],f1[Maxm],f2[Maxm];
15 
16 int dis[Maxn];
17 bool inq[Maxn];
18 queue<int > q;
19 int st,ed,n,m;
20 
21 void spfa()
22 {
23     while(!q.empty()) q.pop();
24     memset(dis,63,sizeof(dis));
25     memset(inq,0,sizeof(inq));
26     q.push(st);dis[st]=0;inq[st]=1;
27     while(!q.empty())
28     {
29         int x=q.front();
30         for(int i=1;i<=m;i++) if((x&b1[i])==b1[i]&&(x&b2[i])==0)
31         {
32             int y=x-(x&f1[i]);
33             y|=f2[i];
34             if(dis[y]>dis[x]+w[i])
35             {
36                 dis[y]=dis[x]+w[i];
37                 if(!inq[y])
38                 {
39                     q.push(y);
40                     inq[y]=1;
41                 }
42             }
43         }
44         q.pop();inq[x]=0;
45     }
46 }
47 
48 char s[30];
49 int main()
50 {
51     scanf("%d%d",&n,&m);
52     for(int i=1;i<=m;i++)
53     {
54         scanf("%d",&w[i]);
55         scanf("%s",s);
56         b1[i]=b2[i]=f1[i]=f2[i]=0;
57         for(int j=0;j<n;j++)
58           if(s[j]==‘+‘) b1[i]+=1<<j;
59           else if(s[j]==‘-‘) b2[i]+=1<<j;
60         scanf("%s",s);
61         for(int j=0;j<n;j++)
62           if(s[j]==‘-‘) f1[i]+=1<<j;
63           else if(s[j]==‘+‘) f2[i]+=1<<j;
64     }
65     st=(1<<n)-1;ed=0;
66     spfa();
67     if(dis[ed]>=INF-100000) printf("0\n");
68     else printf("%d\n",dis[ed]);
69     return 0;
70 }
View Code

 

技术分享

 

2016-11-04 20:24:58

【网络流24题】 No.12 软件补丁问题（最小转移代价 最短路）


联系
我们