The K_n-complement of a graphG, denoted by K_n-G, is defined as the graph obtained from the complete graph K_n by removing a set of edges that span G; if G has n vertices, then K_n-G coincides with the complement G of the graphG. In this paper we extend the previous notion and derive determinant based formulas for the number of spanning trees of graphs of the form K_n^{m} ± G, where K_n^{m} is the complete multigraph on n vertices with exactly m edges joining every pair of vertices and G is a multigraph spanned by a set of edges of K_n^{m}; the graph K_n^m + G (resp. K_n^m - G) is obtained from K_n^{m} by adding (resp. removing) the edges of G. Moreover, we derive determinant based formulas for graphs that result from K_n^{m} by adding and removing edges of multigraphs spanned by sets of edges of the graph K_n^m. We also prove closed formulas for the number of spanning tree of graphs of the form K_{n}^m ± G, where G is (i) a complete multipartite graph, and (ii) a multi-star graph. Our results generalize previous results and extend the family of graphs admitting formulas for the number of their spanning trees.