首页 > 代码库 > Tyvj3308毒药解药题解
Tyvj3308毒药解药题解
题目大意
这些药都有可能在治愈某些病症的同一时候又使人患上某些别的病症……经过我天才的努力。最终弄清了每种药的详细性能,我会把每种药能治的病症和能使人患上的病症列一张清单给你们,然后你们要依据这张清单找出能治愈全部病症的最少药剂组合……顺便说一声,病症的数目不超过10种。我的药是用不完的,就是说每种药剂都能够被反复使用。题解
二进制表示患病状态(2n≤1024 <script type="math/tex" id="MathJax-Element-1">2^n\le1024</script>种)和每种药的治病与致病状态,然后从2n?1 <script type="math/tex" id="MathJax-Element-2">2^n-1</script>到0開始连有向边,然后bfs出最短路就可以。感觉这样对付一道搜索题大材小用了。Code
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 200000, nil = 0, maxm = 21, oo = 1000000000;
int n, m, map[maxm][105];
int cur[105], inf[105];//cure infect
int u[maxn], v[maxn], nxt[maxn], pnt[1 << maxm], e;
bool vis[1 << maxm];
int d[1 << maxm];
void add(int a, int b)
{
u[++e] = a; v[e] = b;
nxt[e] = pnt[a]; pnt[a] = e;
}
void init()
{
int x;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i)
{
for(int j = 1; j <= n; ++j)
{
scanf("%d", &x);
if(x == 1)
{
cur[i] |= (1 << (j - 1));
}
if(x == -1)
{
inf[i] |= (1 << (j - 1));
}
}
}
for(int i = (1 << n) - 1; i > 0; --i)
{
for(int j = 1; j <= m; ++j)
{
add(i, (i & (~cur[j])) | inf[j]);
}
}
}
void work()
{
queue <int> Q;
memset(d, 0x3f, sizeof(d));
Q.push((1 << n) - 1);
d[(1 << n) - 1] = 0;
vis[(1 << n) - 1] = true;
while(!Q.empty())
{
int t = Q.front();
Q.pop();
for(int j = pnt[t]; j != nil; j = nxt[j])
{
if(!vis[v[j]])
{
d[v[j]] = d[t] + 1;
vis[v[j]] = true;
Q.push(v[j]);
}
}
}
if(d[0] > oo) puts("The patient will be dead.");
else printf("%d\n", d[0]);
}
int main()
{
init();
work();
return 0;
}
Tyvj3308毒药解药题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。