Plaster
New
List
Login
c++src
default
shinmera
2019.11.05 10:02:47
#include "../../common.cpp" #include <boost/graph/push_relabel_max_flow.hpp> #include <boost/graph/graphviz.hpp> // Graph Type with nested interior edge properties for flow algorithms typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> traits; typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_capacity_t, int, boost::property<boost::edge_residual_capacity_t, int, boost::property<boost::edge_reverse_t, traits::edge_descriptor>>>> graph; typedef traits::vertex_descriptor vertex_desc; typedef traits::edge_descriptor edge_desc; class edge_adder { graph &G; public: explicit edge_adder(graph &G) : G(G) {} void add_edge(int from, int to, int capacity) { auto c_map = boost::get(boost::edge_capacity, G); auto r_map = boost::get(boost::edge_reverse, G); const auto e = boost::add_edge(from, to, G).first; const auto rev_e = boost::add_edge(to, from, G).first; c_map[e] = capacity; c_map[rev_e] = 0; // reverse edge has no capacity! r_map[e] = rev_e; r_map[rev_e] = e; } }; int main(){ setup(); 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+n+h*w); edge_adder adder(G); int counter = 2; // Edge to target for(int i=0; i<n; ++i){ adder.add_edge(counter++, 1, 1); } // Edge from source for(int i=0; i<h*w; ++i){ adder.add_edge(0, counter++, 1); } // Front vertex int off = n+2; for(int i=0; i<h; ++i){ auto line = read1<std::string>(); for(int j=0; j<w; ++j){ char c = line[j]; for(int k=0; k<n; ++k){ if(note[k] == c) adder.add_edge(off+i*w+j, k+2, 1); } } } // Back vertex for(int i=0; i<h; ++i){ auto line = read1<std::string>(); for(int j=0; j<w; ++j){ char c = line[j]; for(int k=0; k<n; ++k){ if(note[k] == c) adder.add_edge(off+i*w+j, k+2, 1); } } } // if(t==0){ // boost::write_graphviz(std::cout, G); // return 0; // } auto flow = boost::push_relabel_max_flow(G, boost::vertex(0, G), boost::vertex(1, G)); std::cout << ((flow == n)? "Yes" : "No") << '\n'; } }
Raw
Annotate
Repaste