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

【题意】

  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就好了。。。

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

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
#define Maxm 110
#define Maxn 1100000
#define INF 0xfffffff int w[Maxm],b1[Maxm],b2[Maxm],f1[Maxm],f2[Maxm]; int dis[Maxn];
bool inq[Maxn];
queue<int > q;
int st,ed,n,m; void spfa()
{
while(!q.empty()) q.pop();
memset(dis,,sizeof(dis));
memset(inq,,sizeof(inq));
q.push(st);dis[st]=;inq[st]=;
while(!q.empty())
{
int x=q.front();
for(int i=;i<=m;i++) if((x&b1[i])==b1[i]&&(x&b2[i])==)
{
int y=x-(x&f1[i]);
y|=f2[i];
if(dis[y]>dis[x]+w[i])
{
dis[y]=dis[x]+w[i];
if(!inq[y])
{
q.push(y);
inq[y]=;
}
}
}
q.pop();inq[x]=;
}
} char s[];
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d",&w[i]);
scanf("%s",s);
b1[i]=b2[i]=f1[i]=f2[i]=;
for(int j=;j<n;j++)
if(s[j]=='+') b1[i]+=<<j;
else if(s[j]=='-') b2[i]+=<<j;
scanf("%s",s);
for(int j=;j<n;j++)
if(s[j]=='-') f1[i]+=<<j;
else if(s[j]=='+') f2[i]+=<<j;
}
st=(<<n)-;ed=;
spfa();
if(dis[ed]>=INF-) printf("0\n");
else printf("%d\n",dis[ed]);
return ;
}

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

2016-11-04 20:24:58

上一篇:C# Java 3DES加密解密 扩展及修正\0 问题


下一篇:Dubbo源码学习--服务发布(ServiceBean、ServiceConfig)