About the biggest group
This is a typical NP problem. For a long time, I have been thinking about how to solve it until I read a predecessor's recommended document, and I got some inspiration to solve this problem. Problem.
Typical description: given a plurality of Figure G, the Magic Group (the group refers to a full submap of G, which is not included in any other complete sub-map. The biggest group refers to the most upstale group).
The proposition can have many varieties, such as the plug of 1002, 1654, essentially of the biggest group, of course, due to the particularity of the problem, they may also use other more efficient algorithms. After all, the problem is abstract The solution is generally difficult and complexity will increase.
The general algorithm for solving this problem should be a search. It contains a vertex A1, A2, A3, A4, A5 ····. Search from A1, search all the points of the point ... · ····· Typical index time search.
I saw an article that day, I specifically discussed this problem. It is not a method we used to start searching from A1, but in turn, from AN to start, of course, it is only going forward (starting with A5, just search A6, A7 ····· What is the benefit of doing this? In fact, it is similar to dynamic planning so that we can use the search for the next search, and our previous search method basically every search will start to find the most solved. And, we noticed this one of the conclusions: if max [i] indicates the solution to the Search A1, then max [i-1] = max [i] 1 or max [i]. This conclusion is very obvious. If the point of the AI ~ AN may form, the maximum fully shown containing the max [i] contact, the complete sub-graph that A (i-1) to AN can be formed is up to 1 top point than the previous one. These provide a strong constraint for our search.
Here, the Solution source code for ZJU1492 is provided in detail (TLE 2 times, AC once 3.09s):
#include
#include
Int Joint [50] [50];
Int size;
Int max;
INT DP [50];
BOOL FIND;
INT Reachend (int Start, int sets []) // Returns -1 indicates that the adjacent top point set is empty, otherwise the first public vertex is returned.
{
INT LP;
For (lp = start; lp IF (sets [lp]) Return LP; Return -1; } // visit [] represents the neighboring group, Start represents the starting point of the search, remember to search only to the big direction. DEPTH represents the search depth. You can see that we define 2 in the function. A and VISIT [] The same array of content, which mainly takes into account the pointer transmitted by the array, directly uses Visit [] will directly change the contents of Joint neighboring array, and after searching, the status cannot be restored. The reason why it is because SET wants to save information for the next time. SETS is transferred to the backtrach. Void DFS (int visit [], int start, int defst { int loop; Int first; INT sets [50], set [50]; Memcpy (Sets, Visit, Size * 4); Memcpy (Set, Visit, Size * 4); IF ((first = reachend (start, sets)) == - 1) { IF (depth> max) { Max = depth; Find = true; } Return; } While (first! = -1) { IF (DEPTH SIZE-START <= max) // It is not possible to find the most resolved return; IF (DEPTH DP [first] <= max) // cannot find the most solved Return; Sets [first] = 0; SET [first] = 0; // Clear the first point from the adjacent vertices. For (loop = first 1; loop IF (set [loop] == 1 && Joint [first] [loop] == 1) Sets [loop] = 1; Else Sets [loop] = 0; DFS (Sets, First, Depth 1); IF (find) Return; First = reachend (first, set); // update contact } } int main () { Int loop, LP; INT Visit [50]; While (Scanf ("% D", & size)! = EOF && size! = 0) { For (loop = 0; loop For (lp = 0; lp Scanf ("% D", Joint [loop] LP); MAX = 0; For (loop = size-1; loop> = 0; loop -) { Find = false; Memcpy (Visit, Joint [loop], size * 4); DFS (Visit, Loop, 1); DP [loop] = max; } Printf ("% D / N", DP [0]); } Return 0; } Figure we are still represented by adjacent numbers. The biggest difference is that the DFS section can be seen that we don't have a strategy for the entire search once with ordinary DFS, but to the AN, A (N-1), ... ···· A2, A1 to call DFS, This makes it easy we record the results of each search. See the DFS section, the Reachend function is used to determine if the public vertex set is empty, which is empty set, indicating that the leaf joint of the decimal tree is reached, and the result is recorded. Find indicates that this search has been able to get a optimization, you can return, end this search. Otherwise, continue to search. The explanation of the DFS section see the program part. Here, this question is mostly solved. We noticed the main points of this algorithm: From a small to large, the conclusion is used to provide a strong pruning condition for a larger search. This can be said with the top of the top-top practice. This algorithm combines recursive and parents to see the exquisiteness of the algorithm. PS: I have the original article of this algorithm in my hand, I am interested in sending me message. Zju1002 and Zju1654 are essentially such problems, but this method is not recommended because the matrix conversion is more troublesome, so it is not recommended. Xiaojun_wu_5@msn.com (the first issue, limited horizontal, more care)
