您的位置: 首页  >  IT文章  >  P2761 软件补丁问题

P2761 软件补丁问题

分类: IT文章 • 2022-07-22 13:53:30

(color{#0066ff}{题目描述})

T 公司发现其研制的一个软件中有 n 个错误，随即为该软件发放了一批共 m 个补丁程序。每一个补丁程序都有其特定的适用环境，某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时，往往会加入另一些错误。

换句话说，对于每一个补丁 i，都有 2 个与之相应的错误集合 B1[i]和 B2[i]，使得仅当软件包含 B1[i]中的所有错误，而不包含 B2[i]中的任何错误时，才可以使用补丁 i。补丁 i 将修复软件中的某些错误 F1[i]，而同时加入另一些错误 F2[i]。另外，每个补丁都耗费一定的时间。

试设计一个算法，利用 T 公司提供的 m 个补丁程序将原软件修复成一个没有错误的软件，并使修复后的软件耗时最少。对于给定的 n 个错误和 m 个补丁程序，找到总耗时最少的软件修复方案。

(color{#0066ff}{输入格式})

第 1 行有 2 个正整数 n 和 m，n 表示错误总数，m表示补丁总数，1<=n<=20, 1<=m<=100。

接下来 m 行给出了 m 个补丁的信息。每行包括一个正整数，表示运行补丁程序 i 所需时间，以及 2 个长度为 n 的字符串，中间用一个空格符隔开。

第 1 个字符串中，如果第 k 个字符 bk 为“+”，则表示第 k 个错误属于 B1[i]，若为“-”，则表示第 k 个错误属于 B1[i]，若为“0”，则第 k 个错误既不属于 B1[i]也不属于 B2[i]，即软件中是否包含第 k 个错误并不影响补丁 i 的可用性。

第 2 个字符串中，如果第 k 个字符 bk为“-”，则表示第 k 个错误属于 F1[i]，若为“+”，则表示第 k 个错误属于 F2[i]，若为“0”，则第 k 个错误既不属于 F1[i]也不属于 F2[i]，即软件中是否包含第 k 个错误不会因使用补丁i 而改变。

(color{#0066ff}{输出格式})

程序运行结束时，将总耗时数输出。如果问题无解，则输出 0。

(color{#0066ff}{输入样例})

3 3
1 000 00-
1 00- 0-+
2 0-- -++

(color{#0066ff}{输出样例})

8

(color{#0066ff}{数据范围与提示})

none

(color{#0066ff}{题解})

这。。。是网络流？？

状压+最短路啊

瞎搞搞就行了

自以为是的我以为dfs就能水过，然而。。TLE。

把dfs改成dij就行了qwq

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define _ 0
#define LL long long
inline LL in()
{
	LL x=0,f=1; char ch;
	while(!isdigit(ch=getchar()))(ch=='-')&&(f=-f);
	while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
	return x*f;
}
int n,m;
int a[120],b[120],t[120],c[120],d[120];
int dis[1<<21];
bool vis[1<<21];
using std::priority_queue;
using std::pair;
using std::make_pair;
priority_queue<pair<int,int>,std::vector<pair<int,int> >,std::greater<pair<int,int> > > q;
inline char getc()
{
	char ch=getchar();
	while(ch!='0'&&ch!='+'&&ch!='-') ch=getchar();
	return ch;
}
inline bool can(int p,int zt)
{
	for(int i=1;i<=n;i++)
	{
		if((a[p]&(1<<(i-1)))&&(!(zt&(1<<(i-1))))) return false;
		if((b[p]&(1<<(i-1)))&&(zt&(1<<(i-1)))) return false;
	} 
	return true;
}
inline void cov(int p,int &zt)
{
	for(int i=1;i<=n;i++)
	{
		if(c[p]&(1<<(i-1))) if(zt&(1<<(i-1))) zt-=(1<<(i-1));
		if(d[p]&(1<<(i-1))) zt|=(1<<(i-1));
	} 
}
inline void bfs()
{
	int s=(1<<n)-1;
	dis[s]=0;
	q.push(make_pair(dis[s],s));
	while(!q.empty())
	{
		int tp=q.top().second;
		q.pop();
		if(vis[tp]) continue;
		for(int i=1;i<=m;i++)
		{
			int now=tp;
			if(can(i,now))
			{
				cov(i,now);
				if(dis[now]>dis[tp]+t[i])
				{
					dis[now]=dis[tp]+t[i];
					q.push(make_pair(dis[now],now));
				}
			}
		}
	}

}
int main()
{
	n=in(),m=in();
	for(int i=1;i<=m;i++)
	{
		t[i]=in();
		for(int j=1;j<=n;j++)
		{
			char ch=getc();
			if(ch=='+') a[i]|=(1<<(j-1));
			if(ch=='-') b[i]|=(1<<(j-1));
		}
		for(int j=1;j<=n;j++)
		{
			char ch=getc();
			if(ch=='-') c[i]|=(1<<(j-1));
			if(ch=='+') d[i]|=(1<<(j-1));
		}
	}
	memset(dis,0x7f,sizeof dis);
	bfs();
	dis[0]==0x7f7f7f7f? printf("0"):printf("%d",dis[0]);
	return 0;
}

相关推荐