【TopCoder SRM713】DFSCount

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14588&rd=16882

题目大意

给定一个$n(n \le 14)$的简单无向图,问$DFS$序总共可能有多少种不同情况

解题报告

这是一个非常妙妙的$DP$
考虑定义$f_{i,j}$表示当前在第$i$个点,已经走过的点压成二进制状态为$j$
但我们发现这样无法实现$DFS$模拟当中的退回操作

但我们考虑一下$DFS$树:这货是没有横叉边的,只有返祖边
这意味着我们如果决定朝一个方向走,那么一定是把那一个连通块走完才会退回来
于是我么可以不一步一步转移,我们可以把一整块连通块一起转移,这样就不需要模拟$DFS$的回退操作了

至于这份代码是:$O(n^2 2^n)$的
实现得精细一点可以做到$O(n 2^n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
int n,id[15];
bool g[15][15],vis[15];
LL f[15][17000],pw[15],pol[15];

class DFSCount {
    public:
    	long long count(vector<string> G) {
    		pw[0] = 1;
    		for (int i=1;i<=14;i++) {
				pw[i] = pw[i-1] * i;
			}
    	    n = G.size();
    	    for (int i=0;i<n;i++) {
				for (int j=0;j<n;j++) {
					if (G[i][j] == 'Y') g[i][j] = 1;
					else g[i][j] = 0;
				}
			}
    	    memset(f, 0, sizeof(f));
			for (int i=0;i<n;i++) {
				f[i][(1<<n)-1] = 1;
			}
			for (int sta=(1<<n)-2;sta>0;sta--) {
				for (int i=0;i<n;i++) {
					if (!(sta&(1<<i))) continue;
					for (int j=0;j<n;j++) {
						vis[j] = (sta & (1 << j));
					}
					int cnt = 0;
					for (int j=0;j<n;j++) {
						if (g[i][j] && !(sta&(1<<j))) {
							if (!vis[j]) {
								DFS(j, ++cnt);
								pol[cnt] = 0;
							}
							pol[id[j]] += f[j][(1<<j)|sta];
						}
					}
					f[i][sta] = pw[cnt];
					for (int j=1;j<=cnt;j++) {
						f[i][sta] *= pol[j];
					}
				}
			}
			LL ret = 0;
			for (int i=0;i<n;i++) {
				ret += f[i][1<<i];
			}
			return ret;
   		}
   	private:
   		void DFS(int w, int ID) {
			vis[w] = 1; 
			id[w] = ID;
			for (int i=0;i<n;i++) {
				if (g[w][i] && !vis[i]) {
					DFS(i, ID);
				} 
			}   
		}
};

21 thoughts to “【TopCoder SRM713】DFSCount”

  1. Hmm it appears like your website ate my first comment (it was extremely long) so I guess I’ll just
    sum it up what I wrote and say, I’m thoroughly enjoying your blog.
    I as well am an aspiring blog blogger but I’m still new to the whole thing.

    Do you have any suggestions for inexperienced blog
    writers? I’d definitely appreciate it.

  2. You actually make it seem so easy with your presentation but I find this topic
    to be actually something that I think I would never
    understand. It seems too complex and extremely broad for me.
    I am looking forward for your next post, I’ll try to get the hang of
    it!

  3. Today, I went to the beach with my kids. I found a sea shell
    and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.”
    She placed the shell to her ear and screamed.
    There was a hermit crab inside and it pinched her ear.
    She never wants to go back! LoL I know this is totally off topic but I had to
    tell someone!

  4. Please let me know if you’re looking for
    a writer for your blog. You have some really great posts and
    I feel I would be a good asset. If you ever want to take some of the
    load off, I’d absolutely love to write some material for your blog in exchange for a link back to
    mine. Please blast me an email if interested.
    Kudos!

  5. Hello, i think that i saw you visited my web site thus i came to “return the favor”.I’m trying to find things to enhance my web
    site!I suppose its ok to use some of your ideas!!

  6. I do believe all the ideas you have introduced on your
    post. They’re really convincing and can certainly
    work. Still, the posts are very quick for beginners.
    May you please prolong them a little from next time?
    Thank you for the post.

  7. Appreciating the time and effort you put into your blog and in depth information you present.
    It’s awesome to come across a blog every once in a while that isn’t
    the same old rehashed information. Excellent read! I’ve saved your site
    and I’m including your RSS feeds to my Google account.

  8. I haven’t checked in here for a while as I thought it was getting boring, but the last few posts are great quality so I guess I will add you back to my everyday bloglist. You deserve it my friend 🙂

  9. What i don’t understood is in fact how you are no longer really a lot more smartly-liked than you might
    be now. You are so intelligent. You know therefore
    considerably when it comes to this matter, produced me personally believe it from numerous varied angles.
    Its like women and men aren’t fascinated except it is one thing to accomplish with Girl gaga!
    Your personal stuffs excellent. All the time care for it up!

  10. certainly like your web site but you have to check the spelling on quite a few of your
    posts. Many of them are rife with spelling
    problems and I find it very troublesome to inform the truth then again I’ll definitely come again again.

  11. Valuable info. Fortunate me I discovered your site by
    accident, and I’m stunned why this coincidence did not took place in advance!
    I bookmarked it.

  12. I loved as much as you’ll receive carried out right here.
    The sketch is attractive, your authored material stylish.
    nonetheless, you command get got an nervousness over that you wish be delivering
    the following. unwell unquestionably come more formerly again as exactly the same nearly very often inside case you shield this increase.

  13. Pretty nice post. I just stumbled upon your blog and wished
    to say that I have really enjoyed surfing around your weblog posts.
    After all I will be subscribing on your feed and
    I’m hoping you write again soon!

  14. Everything is very open with a precise clarification of the
    challenges. It was truly informative. Your site is very useful.
    Thank you for sharing!

  15. Its like you read my mind! You appear to know a lot
    about this, like you wrote the book in it
    or something. I think that you can do with some pics to drive the message home a bit, but instead of that,
    this is fantastic blog. An excellent read.

    I’ll definitely be back.

  16. fantastic publish, very informative. I wonder why the opposite experts of this sector do not notice this.
    You must continue your writing. I am sure, you’ve a huge readers’ base
    already!

发表评论

电子邮件地址不会被公开。 必填项已用*标注