Plaster
New
List
Login
c++src
default
shinmera
2019.11.07 10:19:54
int main(){ setup(); int offset = 'A'; int letters = 'Z' - 'A'; auto t = read1<int>(); while(0 < t--){ auto h = read1<int>(); auto w = read1<int>(); auto note = read1<std::string>(); int n = note.size(); graph G(2+letters+h*w); edge_adder adder(G); auto source = boost::vertex(0, G); auto target = boost::vertex(1, G); // Edge for every letter (letter -> target [num]) for(int i=0; i<letters; ++i){ // Count letters int count = 0; for(int j=0; j<n; ++j) if(note[j]-offset == i) ++count; if(0 < count) adder.add_edge(2+i, target, count); } // Edge for every snippet (source -> snippet [1]) for(int i=0; i<h*w; ++i) adder.add_edge(source, 2+letters+i, 1); // Connect snippet to front letter (snippet -> letter [1]) for(int i=0; i<h; ++i){ auto line = read1<std::string>(); for(int j=0; j<w; ++j) adder.add_edge(2+letters+i*w+j, line[j]+2-offset, 1); } // Connect snippet to back letter (snippet -> letter [1]) for(int i=0; i<h; ++i){ auto line = read1<std::string>(); for(int j=0; j<w; ++j) adder.add_edge(2+letters+i*w+(w-j-1), line[j]+2-offset, 1); } // boost::write_graphviz(std::cout, G); // return 0; auto flow = boost::push_relabel_max_flow(G, source, target); std::cout << ((flow == n)? "Yes" : "No") << '\n'; } }
Raw
Annotate
Repaste