It's not a Bug, It's a Feature! (poj 1482 最短路SPFA+隐式图+位运算)
Language:
Default
It's not a Bug, It's a Feature!
Description
It is a curious fact that consumers buying a new software product generally do not expect the software to be bug-free. Can you imagine buying a car whose steering wheel only turns to the right?
Or a CD-player that plays only CDs with country music on them? Input
The input contains several product descriptions. Each description starts with a line containing two integers n and m, the number of bugs and patches, respectively. These values satisfy 1 <= n <= 20 and 1 <= m <= 100. This is followed by m lines describing the
m patches in order. Each line contains an integer, the time in seconds it takes to apply the patch, and two strings of n characters each. The first of these strings describes the bugs that have to be present or absent before the patch can be applied. The i-th position of that string is a ``+'' if bug bi has to be present, a ``-'' if bug bi has to be absent, and a `` 0'' if it doesn't matter whether the bug is present or not. The second string describes which bugs are fixed and introduced by the patch. The i-th position of that string is a ``+'' if bug bi is introduced by the patch, a ``-'' if bug bi is removed by the patch (if it was present), and a ``0'' if bug bi is not affected by the patch (if it was present before, it still is, if it wasn't, is still isn't). The input is terminated by a description starting with n = m = 0. This test case should not be processed. Output
For each product description first output the number of the product. Then output whether there is a sequence of patches that removes all bugs from a product that has all n bugs. Note that in such a sequence a patch may be used multiple times. If there is such
a sequence, output the time taken by the fastest sequence in the format shown in the sample output. If there is no such sequence, output ``Bugs cannot be fixed.''. Print a blank line after each test case. Sample Input 3 3 Sample Output Product 1 Source |
这个题拿到手并不会做,没有好的思路,然后就看了网上的题解。第一次碰到不建图也能SPFA的,又学习了。另外这一题的位运算处理也非常巧妙,这是我不熟悉的,先放在这里,以后多来看几遍。
參考这两篇博客,写的非常好:http://www.cnblogs.com/scau20110726/archive/2012/12/16/2820739.html
http://www.cnblogs.com/staginner/archive/2011/10/25/2223489.html
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b) for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b) for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf printf
#define DBG pf("Hi\n")
typedef long long ll;
using namespace std; #define INF 0x3f3f3f3f
#define mod 1000000009
const int maxn = 25;
const int MAXN = 111;
const int MAXM = (1<<20)+100;
const int N = 1005; char s1[maxn],s2[maxn];
int s[2][MAXN],t[2][MAXN],cost[MAXN];
int dist[MAXM];
bool inq[MAXM];
int n,m; void SPFA()
{
int i,j;
mem(inq,false);
mem(dist,INF);
queue<int>Q;
int start=(1<<n)-1;
Q.push(start);
inq[start]=true;
dist[start]=0;
while (!Q.empty())
{
int u=Q.front(); Q.pop();
inq[u]=false;
for (i=0;i<m;i++)
{
if ((u|s[1][i])==u&&(u&s[0][i])==u)
{
int v=u;
v|=t[1][i];
v&=t[0][i];
if (dist[v]>dist[u]+cost[i])
{
dist[v]=dist[u]+cost[i];
if (!inq[v])
{
inq[v]=true;
Q.push(v);
}
}
}
}
}
// for(i=0;i<=start;i++)
// pf("%d ",dist[i]);
// pf("\n");
if (dist[0]==INF)
pf("Bugs cannot be fixed.\n");
else
pf("Fastest sequence takes %d seconds.\n",dist[0]);
} int main()
{
#ifndef ONLINE_JUDGE
freopen("C:/Users/lyf/Desktop/IN.txt","r",stdin);
#endif
int i,j,cas=0;
while (sff(n,m))
{
if (n==0&&m==0) break;
mem(s,0);
mem(t,0);
for (i=0;i<m;i++)
{
scanf("%d%s%s",&cost[i],s1,s2);
for (j=0;j<n;j++)
{
if (s1[j]=='+')
s[1][i]+=(1<<j);
if (s1[j]!='-')
s[0][i]+=(1<<j);
if (s2[j]=='+')
t[1][i]+=(1<<j);
if (s2[j]!='-')
t[0][i]+=(1<<j);
}
}
pf("Product %d\n",++cas);
SPFA();
pf("\n");
}
return 0;
}
最新文章
- jQuery使用示例详解
- 我的Github注册使用之旅
- php头像上传并裁剪支持3个尺寸
- php 同步因子的并发处理
- Font-Awesome for android
- 在ubuntu下安装chrome
- 小游戏 Lights Out (关灯) 的求解 —— 异或方程组
- ItextSharp代码示例
- Jsonql——给RESTful API插上一对翅膀
- NYOJ--714--Card Trick
- Python基本格式化输出
- Taurus.MVC 支持Asp.Net Core 的过程
- SpringBoot 多数据源分布式事务
- docker 给none镜像打镜像
- jquery.zclip.js粘贴功能
- 9.8 翻译系列:数据注解特性之--Required 【EF 6 Code-First系列】
- node(3)Buffer缓冲区
- Redis集群错误
- Linux 操作MySQL常用命令行(转)
- Ubuntu下更改Vim配置文件打造C/C++风格
热门文章
- Laravel5.1学习笔记18 数据库4 数据填充
- [ ZJOI 2006 ] Mahjong
- SSH Secure Shell Client连接centos6.5时中文字乱码处理
- 【译】x86程序员手册05 - 2.3寄存器
- VHDL之Serial-Parallel Multiplier
- HDU_1027_Ignatius and the Princess II_全排列
- 发布自己的nuget包
- CAD保存DWG文件,设置保存的文件版本号和密码
- vivado2018.3 与 modelsim联合仿真
- Beauty of Array ZOJ - 3872(思维题)