D. A Simple Task
题意
求出一个n个点m个边的图,求简单环有多少(没有重复点和边)。(n<20)
题解
用S能记录状态(有多少个点在路径中),那么如何找环能确保不重不漏啦,对于一个环,找出他的特异性记录,一个环,如果以最小点为环的“起始点”,则每个环都被记录啦两次。用dp[s][i]表示路径s的当前点为i的次数,枚举下一点,如果形成环就加上答案,否则记录下一边。由于题目求的是超过三个点的简单环,而之前所求两个点也会被记录。减掉就可以啦。
代码
1 |
|
求出一个n个点m个边的图,求简单环有多少(没有重复点和边)。(n<20)
用S能记录状态(有多少个点在路径中),那么如何找环能确保不重不漏啦,对于一个环,找出他的特异性记录,一个环,如果以最小点为环的“起始点”,则每个环都被记录啦两次。用dp[s][i]表示路径s的当前点为i的次数,枚举下一点,如果形成环就加上答案,否则记录下一边。由于题目求的是超过三个点的简单环,而之前所求两个点也会被记录。减掉就可以啦。
1 | #include <bits/stdc++.h> |