相关链接
题目传送门: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); } } } };
楼下是疯子。哈哈
It’s awesome to go to see this web site and reading the views of all mates about this piece of writing, while I am also keen of getting know-how.
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.
WOW just what I was looking for. Came here by searching for coconut
oil of
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!
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!
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!
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!!
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.
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.
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 🙂
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!
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.
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.
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.
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!
Everything is very open with a precise clarification of the
challenges. It was truly informative. Your site is very useful.
Thank you for sharing!
Great article, exactly what I was looking for.
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.
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!
Hello, constantly i used to check web site posts here early in the
dawn, for the reason that i love to gain knowledge of more
and more.
Terrific article! This is the kind of info that are supposed to be shared across the net.
Disgrace on Google for not positioning this post higher!
Come on over and seek advice from my website .
Thank you =)
Some truly nice stuff on this web site, I enjoy it.