给你 n 个串,和 m 个病毒串。要把这 n 个串连起来来,可以重叠,但不能包含 m 个病毒串中的任意一个。求把 n 个串连起来的最小长度。
#include <iostream>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;
int const N= 1010, M= 60010;
int n, m, cnt, bit[15];
char str[N];
struct Trie{
int next[2];
int fail, end;
void init(){
fail= -1; end= 0;
next[0]= 0; next[1]= 0;
}
}tb[M];
inline void insert( char* s, int d ){
int rt= 0;
while( *s ){
int t= *s- '0';
if( tb[rt].next[t]== 0 ){
tb[++cnt].init();
tb[rt].next[t]= cnt;
}
rt= tb[rt].next[t]; s++;
}
tb[rt].end= d;
}
int que[M], head, tail;
void bfs(){
int q, p;
head= 0, tail= 0; que[0]= 0;
while( head<= tail ){
int now= que[head++];
for( int t= 0; t< 2; ++t )
if( tb[now].next[t] ){
p= tb[now].next[t]; q= tb[now].fail;
while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
if( q== -1 ) tb[p].fail= 0;
else tb[p].fail= tb[q].next[t];
que[++tail]= p;
}
else{
q= tb[now].fail;
while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
if( q== -1 ) tb[now].next[t]= 0;
else tb[now].next[t]= tb[q].next[t];
}
}
}
struct Node{
int steps, state, node;
Node(){}
Node( int x, int y, int z ):
node( x ), steps(y), state(z) {}
};
bitset<(1<<10)> flag[M];
int solve(){
queue<Node> q; q.push( Node(0,0,0) );
flag[0][0]= 1;
while( !q.empty() ){
Node now= q.front(); q.pop();
for( int t= 0; t< 2; ++t )
if( tb[ tb[ now.node ].next[t] ].end>= 0 ){
Node tmp= now;
tmp.node= tb[ now.node ].next[t];
tmp.steps+= 1;
if( tb[ tmp.node ].end> 0 )
tmp.state|= bit[ tb[tmp.node].end- 1 ];
if( tmp.state== bit[n]- 1 ) return tmp.steps;
if( flag[ tmp.node ][ tmp.state ] ) continue;
flag[ tmp.node ][ tmp.state ]= 1;
q.push( tmp );
}
}
return -1;
}
int main(){
for( int i= 0; i<= 10; ++i ) bit[i]= 1<<i;
while( scanf("%d%d",&n,&m)!= EOF ){
if( n== 0 && m== 0 ) return 0;
cnt= 0; tb[0].init();
for( int i= 1; i<= n; ++i ){
scanf("%s", str );
insert( str, i );
}
for( int i= 1; i<= m; ++i ){
scanf("%s", str );
insert( str, -1 );
}
bfs();
for( int i= 0; i<= cnt; ++i ) flag[i].reset();
int ans= 0;
ans= solve();
printf("%d\n", ans );
}
return 0;
}
分享到:
相关推荐
ZJU/zoj 题库上的部分题源码 本人博客: hi.baidu.com/xiaoxianxi_acm
acm 新手必备 浙大 解答 代码库 zoj zju
zoj 1140-zju 2433 简单题的部分答案 都是可以正确通过的,简洁易懂
acm 模板 算法 浙大 zoj zju acm初学者必备 代码
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
http://acm.zju.edu.cn/ acm的AC解题报告
ZOJ是一个经典的分油问题,我再这里采用的是广度优先的方法,当然得到的不是最优解,只是一个可行解而已。
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
最近在acm.zju.edu.cn上通过的题目的代码,都是比较有价值的题目
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
zoj上的3607Lazier Salesgirl AC代码及一些注释。贪心算法
Problem Arrangement zoj 3777
ZOJ题目答案源码
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
一个非常非常非常非常实用的zoj结题代码
能AC 通过的c++代码,包括zoj1002,1091,1789
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复