UVA658-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? Probably not. But for software systems
it seems to be acceptable if they do not perform as they should do. In fact, many software companies
have adopted the habit of sending out patches to fix bugs every few weeks after a new product is
released (and even charging money for the patches).
Tinyware Inc. is one of those companies. After releasing a new word processing software this
summer, they have been producing patches ever since. Only this weekend they have realized a big
problem with the patches they released. While all patches fix some bugs, they often rely on other bugs
to be present to be installed. This happens because to fix one bug, the patches exploit the special
behavior of the program due to another bug.
More formally, the situation looks like this. Tinyware has found a total of n bugs
B
=
b
1
,
b
2
,
.
.
.
,
b
n
in their software. And they have released m patches
p
1
,
p
2
,
.
.
.
,
p
m
.
To apply patch pi to the software,
the bugs