题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2595
数据生成器：http://paste.ubuntu.com/23070779/
斯坦纳树第一题！ 撒花~ *★,°*:.☆(￣▽￣)/$:*.°★* 。
然而感觉斯坦纳树，撑死了算一类DP问题，为什么要叫算法呢QAQ
其实斯坦纳树，说白了就是一个状压DP？
题解的话，让我们召唤神犇：http://www.cnblogs.com/lidaxin/p/5299762.html
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define id(x,y) (((y)-1)*n+(x))
using namespace std;
const int MAXN = 19*19;
const int N = 2500;
const int INF = 0x3f3f3f3f;
int n,m,cnt,mat[MAXN],f[MAXN][N],num[MAXN],X,Y,vis[MAXN][N],pv,avl[MAXN];
queue<pair<int,int> > que;
pair<int,int> from[MAXN][N];
inline int read(){
char c=getchar(); int ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret;
}
inline void rev(int w){
Y = w / n + 1;
X = w - (Y-1)*n;
if (!X) X = n, Y--;
}
inline void update(int op, int nv, int pos, int w){
if (f[pos][w] > nv) {
f[pos][w] = nv;
from[pos][w] = make_pair(op,w);
if (!vis[pos][w]) vis[pos][w] = 1, que.push(make_pair(pos,w));
}
}
inline void SPFA(){
while (!que.empty()) {
rev(que.front().first);
int x=X, y=Y, w=que.front().second, pos=que.front().first;
vis[pos][w] = 0; que.pop();
if (x > 1) update(pos,f[pos][w]+mat[id(x-1,y)],id(x-1,y),w);
if (y > 1) update(pos,f[pos][w]+mat[id(x,y-1)],id(x,y-1),w);
if (x < n) update(pos,f[pos][w]+mat[id(x+1,y)],id(x+1,y),w);
if (y < m) update(pos,f[pos][w]+mat[id(x,y+1)],id(x,y+1),w);
}
}
inline void Steiner_Tree(){
for (int w=1,lim=1<<cnt;w<lim;w++) {
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) {
for (int k=w&(w-1);k;k=w&(k-1)) {
int tmp = f[id(i,j)][k] + f[id(i,j)][w^k] - mat[id(i,j)];
if (f[id(i,j)][w] > tmp) f[id(i,j)][w] = tmp, from[id(i,j)][w] = make_pair(id(i,j),k);
}
if (f[id(i,j)][w] != INF) que.push(make_pair(id(i,j),w)), vis[id(i,j)][w] = 1;
} SPFA();
}
}
void Mark_Ans(pair<int,int> tmp){
int pos=tmp.first, w = tmp.second; if (!pos) return;
rev(pos); int x = X, y = Y; avl[id(x,y)] = 1;
Mark_Ans(from[pos][w]);
if (from[pos][w].first == pos) Mark_Ans(make_pair(id(x,y),w-from[pos][w].second));
}
int main(){
m = read(); n = read();
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) {
memset(f[id(i,j)],0x3f,sizeof(f[id(i,j)]));
f[id(i,j)][0] = 0; mat[id(i,j)] = read();
if (!mat[id(i,j)]) f[id(i,j)][1<<cnt++] = 0, pv = id(i,j);
}
Steiner_Tree(); Mark_Ans(make_pair(pv,(1<<cnt)-1));
printf("%d\n",f[pv][(1<<cnt)-1]);
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++)
if (!mat[id(i,j)]) putchar('x');
else if (avl[id(i,j)]) putchar('o');
else putchar('_');
putchar('\n');
}
return 0;
}
Asking questions are really nice thing if you
are not understanding anything fully, but this paragraph gives good understanding yet.
I’m really enjoying the design and layout of your website.
It’s a very easy on the eyes which makes it much more enjoyable for me to come here and visit more often. Did you hire
out a designer to create your theme? Excellent work!
My developer is trying to persuade me to move to .net from PHP.
I have always disliked the idea because of the costs.
But he’s tryiong none the less. I’ve been using WordPress on a number
of websites for about a year and am nervous about
switching to another platform. I have heard very good things about blogengine.net.
Is there a way I can transfer all my wordpress posts
into it? Any help would be greatly appreciated!
Your way of explaining the whole thing in this paragraph is genuinely nice,
all be capable of simply know it, Thanks a lot.
It’s genuinely very complex in this busy life to listen news on Television,
thus I simply use web for that reason, and obtain the
latest news.
Hi, Neat post. There’s a problem together with your web site in web explorer, could test this?
IE nonetheless is the market leader and a big part of folks will pass over your wonderful
writing because of this problem.
Hi there, i read your blog from time to time and i own a similar one and i was
just curious if you get a lot of spam remarks?
If so how do you protect against it, any plugin or anything you can suggest?
I get so much lately it’s driving me mad so any support is very much appreciated.
Greetings I am so happy I found your web site, I really found you by error, while I was searching on Aol for something else, Regardless I am here now and would just like to say thank you
for a tremendous post and a all round thrilling blog (I also love the theme/design), I don’t have
time to browse it all at the moment but I have bookmarked it and also included your
RSS feeds, so when I have time I will be back to read
much more, Please do keep up the awesome job.
I all the time used to study post in news papers but now as
I am a user of web so from now I am using net for articles or reviews, thanks to
web.
Hi there, just became aware of your blog through Google, and found that it
is really informative. I am gonna watch out for brussels.
I’ll be grateful if you continue this in future.
Numerous people will be benefited from your writing.
Cheers!
Fascinating blog! Is your theme custom made or did you download it from somewhere?
A design like yours with a few simple adjustements would really make my blog stand out.
Please let me know where you got your design. Thank you
An outstanding share! I’ve just forwarded this onto a co-worker who has been conducting a little homework on this.
And he in fact ordered me breakfast because I discovered it for him…
lol. So allow me to reword this…. Thank YOU for the meal!!
But yeah, thanx for spending some time to talk about this matter here
on your website.
Hey there! This is my first comment here so I just wanted to give a quick shout out and tell
you I truly enjoy reading through your posts.
Can you recommend any other blogs/websites/forums that cover
the same topics? Thanks for your time!
Nice post. I was checking constantly this blog and I am impressed!
Extremely useful info specially the last part 🙂 I care for such info a lot.
I was seeking this certain information for a long time.
Thank you and good luck.
Very descriptive article, I loved that a lot. Will there be a part
2?
Hello there, There’s no doubt that your website
could possibly be having browser compatibility problems.
Whenever I look at your site in Safari, it looks fine however when opening in Internet Explorer, it’s got some overlapping issues.
I merely wanted to provide you with a quick heads up!
Other than that, fantastic blog!
Hello friends, how is the whole thing, and what you desire to
say on the topic of this article, in my view its truly amazing for me.
Hi, I do believe this is an excellent website.
I stumbledupon it 😉 I’m going to revisit yet again since i
have book-marked it. Money and freedom is the greatest way
to change, may you be rich and continue to guide
other people.
Hola! I’ve been reading your website for a long time now
and finally got the courage to go ahead and give you a shout out from Porter Tx!
Just wanted to say keep up the great work!
You made some decent points there. I looked on the internet to learn more about the issue and
found most individuals will go along with your views on this website.
plenty of fish natalielise
We are a group of volunteers and opening a new scheme in our community.
Your web site provided us with valuable info to work on. You have done
a formidable job and our whole community will be thankful to you.
When some one searches for his necessary thing, thus he/she desires to
be available that in detail, therefore that thing is maintained over here.
Greetings I am so grateful I found your website,
I really found you by accident, while I was browsing on Aol for something else, Regardless I
am here now and would just like to say cheers for a remarkable post and a all round entertaining
blog (I also love the theme/design), I don’t have time to browse it all at the moment but I have bookmarked it and also
included your RSS feeds, so when I have time I will be back to
read a lot more, Please do keep up the great work. plenty of fish
natalielise
It’s really a nice and helpful piece of info. I’m
glad that you shared this helpful information with us.
Please stay us informed like this. Thank you for sharing.
Hi there! I just wanted to ask if you ever have any problems with hackers?
My last blog (wordpress) was hacked and I ended up losing months of hard
work due to no back up. Do you have any methods to protect
against hackers? pof natalielise
Appreciate this post. Let me try it out.
First of all I want to say fantastic blog! I had
a quick question that I’d like to ask if you don’t mind.
I was curious to find out how you center yourself and clear your mind
prior to writing. I’ve had difficulty clearing my thoughts in getting my
ideas out there. I truly do enjoy writing however it just seems like the first 10 to 15 minutes tend to be lost just trying to figure out
how to begin. Any recommendations or hints? Thank you!
natalielise pof
For hottest news you have to pay a quick visit internet and on world-wide-web I found this website as a best
website for most up-to-date updates.
Hello to all, since I am in fact eager of reading this web site’s post
to be updated regularly. It includes fastidious material.
Heya! I just wanted to ask if you ever have
any trouble with hackers? My last blog (wordpress) was hacked and I ended up losing months of hard work due
to no back up. Do you have any methods to protect against hackers?
Definitely believe that which you stated. Your favorite reason appeared to be at the internet the easiest factor
to consider of. I say to you, I definitely
get annoyed at the same time as people consider worries that they
plainly don’t realize about. You managed to hit the nail upon the highest as smartly as defined
out the whole thing without having side effect , other people can take a signal.
Will probably be back to get more. Thanks
Hey there! I’m at work surfing around your blog from my new iphone 3gs!
Just wanted to say I love reading through your blog and look forward
to all your posts! Keep up the excellent work!
I’ve been surfing on-line more than three hours lately,
but I by no means found any attention-grabbing article like yours.
It’s pretty value enough for me. In my opinion, if all webmasters
and bloggers made excellent content material as you probably did, the web will likely be a
lot more useful than ever before.
Hi there i am kavin, its my first time to commenting anyplace, when i read this article i thought i could also make comment due to this
brilliant paragraph.
Unquestionably believe that which you stated. Your favorite justification seemed to be
on the net the simplest thing to be aware of. I say to you,
I certainly get irked while people consider worries that they just do not
know about. You managed to hit the nail upon the top and
also defined out the whole thing without having side-effects ,
people can take a signal. Will probably be back to get more.
Thanks
These are in fact fantastic ideas in on the topic of blogging.
You have touched some pleasant things here. Any way keep up wrinting.
Pretty! This was a really wonderful post. Many
thanks for supplying this information.
I was more than happy to uncover this web site. I need
to to thank you for ones time for this particularly wonderful read!!
I definitely enjoyed every part of it and i also
have you saved to fav to look at new things on your website.
Hi to all, how is the whole thing, I think every one is getting more from this website, and your
views are nice in support of new people.
Heya i am for the first time here. I found this board and I find It really useful &
it helped me out a lot. I hope to give something back and help
others like you aided me.
It’s an awesome post in favor of all the web people;
they will obtain advantage from it I am sure.
For most recent information you have to go to see
world wide web and on internet I found this site as a most
excellent web site for latest updates.
Very energetic post, I enjoyed that bit. Will there be a
part 2?
Good day! Would you mind if I share your blog with my facebook group?
There’s a lot of people that I think would really
enjoy your content. Please let me know. Thank you
Very rapidly this web site will be famous amid all blogging visitors, due to it’s fastidious articles
For newest information you have to pay a visit internet and on web I found this website as a most excellent web site for most up-to-date updates.
Thank you for the auspicious writeup. It in truth was a entertainment account it.
Look complicated to more brought agreeable from you! However, how can we keep up a
correspondence?
Greetings from Los angeles! I’m bored at work so
I decided to check out your blog on my iphone during lunch break.
I love the knowledge you provide here and can’t wait to take a
look when I get home. I’m amazed at how quick your blog loaded
on my phone .. I’m not even using WIFI, just
3G .. Anyways, very good blog!
I all the time used to study piece of writing in news papers but
now as I am a user of internet so from now I am using net for posts, thanks to
web.
Just want to say your article is as surprising. The clearness in your post is just great
and i can assume you’re an expert on this subject. Fine with your permission allow me to grab your RSS feed to keep updated with forthcoming post.
Thanks a million and please continue the enjoyable
work.
It’s a pity you don’t have a donate button! I’d most certainly donate to this excellent
blog! I suppose for now i’ll settle for bookmarking and adding
your RSS feed to my Google account. I look forward to fresh
updates and will share this website with my Facebook group.
Talk soon!
I’ve been exploring for a little bit for any high quality articles or weblog posts
on this sort of space . Exploring in Yahoo I eventually stumbled upon this website.
Reading this info So i am happy to exhibit that I’ve an incredibly just right uncanny
feeling I found out exactly what I needed.
I such a lot for sure will make sure to don?t forget this web site and provides it a look regularly.
Whats up this is kind of of off topic but I was wondering if
blogs use WYSIWYG editors or if you have to manually code with HTML.
I’m starting a blog soon but have no coding expertise so I wanted to get advice from someone with experience.
Any help would be greatly appreciated!
Greetings! Very helpful advice within this article! It is the little changes which will make the
biggest changes. Many thanks for sharing!
Excellent, what a web site it is! This web site provides useful data to
us, keep it up.
My brother recommended I may like this website. He used to
be totally right. This publish truly made my day.
You can not consider just how a lot time I had spent for this information! Thanks!
If some one wants to be updated with latest technologies
after that he must be visit this site and be up to date daily.
You could definitely see your enthusiasm in the work you write.
The arena hopes for more passionate writers such as you who are not afraid to mention how they believe.
Always follow your heart.
Fantastic post however I was wanting to know if you could write a litte more on this subject?
I’d be very grateful if you could elaborate a little bit further.
Appreciate it!
Thanks designed for sharing such a fastidious opinion, paragraph is fastidious, thats
why i have read it completely
Greetings from Los angeles! I’m bored at work so I decided to check out
your blog on my iphone during lunch break. I really
like the information you present here and can’t wait
to take a look when I get home. I’m surprised at how fast your
blog loaded on my mobile .. I’m not even using WIFI, just 3G ..
Anyways, great site!
Greetings! Quick question that’s entirely off topic.
Do you know how to make your site mobile friendly? My site looks weird when viewing from my apple iphone.
I’m trying to find a template or plugin that might be able to fix this
issue. If you have any recommendations, please share.
Many thanks!
Hi there to all, how is the whole thing, I think every one is getting more from
this website, and your views are pleasant for new people.
I am really impressed with your writing skills as well as with the layout
on your weblog. Is this a paid theme or did you customize it yourself?
Anyway keep up the nice quality writing, it is rare to see a great blog like this one today.
Hello mates, fastidious piece of writing and nice arguments
commented at this place, I am really enjoying by these.
I absolutely love your blog.. Great colors & theme.
Did you make this site yourself? Please reply back as I’m attempting to create my own site
and want to find out where you got this from or what the theme is named.
Appreciate it!
Hello my loved one! I want to say that this article is awesome, nice written and come with approximately all significant
infos. I would like to look extra posts like this .
Hi, I think your site might be having browser compatibility issues.
When I look at your website in Safari, it looks fine but when opening in Internet Explorer, it
has some overlapping. I just wanted to give
you a quick heads up! Other then that, very good blog!
Thank you for another informative website. The place else may just I am getting that kind of information written in such
an ideal manner? I have a challenge that I’m just now running on, and I’ve been on the glance out for such info.
Wow, awesome blog layout! How lengthy have you ever been blogging for?
you make running a blog glance easy. The entire glance of your web site is wonderful, let alone the content!
I always spent my half an hour to read this web site’s content all the
time along with a cup of coffee.
Great article! That is the kind of information that are supposed to be shared across the net.
Shame on Google for now not positioning this put up upper!
Come on over and talk over with my web site . Thanks =)
Hey there! I simply would like to give you a huge thumbs up for your
great info you have here on this post. I am coming back to your web site for more soon.
Hello, Neat post. There is an issue along with your web site in web explorer,
may check this? IE nonetheless is the market chief and
a huge component of other folks will leave out your fantastic writing due to this problem.
Hi! I’m at work surfing around your blog from my new iphone!
Just wanted to say I love reading through your blog and look forward
to all your posts! Keep up the excellent work!
Appreciation to my father who stated to me on the topic of this website, this weblog is genuinely amazing.
Awesome website you have here but I was curious if you knew of any
forums that cover the same topics discussed here? I’d really like to
be a part of online community where I can get opinions from
other knowledgeable people that share the same interest.
If you have any recommendations, please let me know. Kudos!
Very good blog! Do you have any recommendations for aspiring writers?
I’m planning to start my own blog soon but I’m a little lost on everything.
Would you propose starting with a free platform like WordPress or
go for a paid option? There are so many choices out there that I’m completely confused
.. Any ideas? Thank you!
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 could do with a few pics to drive the message home a little
bit, but other than that, this is excellent blog.
A great read. I will definitely be back.
Keep this going please, great job!
Wow, this piece of writing is nice, my sister is analyzing these things, thus I am going
to let know her.
Hi there it’s me, I am also visiting this site on a regular
basis, this website is actually fastidious and the
users are in fact sharing good thoughts.
When some one searches for his vital thing, therefore he/she desires to be available that in detail,
therefore that thing is maintained over here.
Does your website have a contact page? I’m having problems locating it but, I’d like to shoot you an e-mail.
I’ve got some suggestions for your blog you
might be interested in hearing. Either way, great blog and I look
forward to seeing it improve over time.
Thanks to my father who shared with me concerning this weblog,
this blog is really amazing.