【BZOJ 3534】[Sdoi2014] 重建

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3534
矩阵树定理基础:http://oi.cyo.ng/?p=717

解题报告

说明:以下使用变量名,均同上面的矩阵树定理基础

这个题目直接看矩阵树定理肯定是没有头绪的。
但如果我们看矩阵树定理推导过程中的这个式子:\(\partial = {\sum\limits_{G’isG’sSubgraph} {\det (M(G’))} ^2}\)
不难发现我们可以这样算贡献:\(\partial = {\sum\limits_{G’isG’sSubgraph} {\det (M(G’))} ^2} \cdot P\)
其中p为,在生成树中的点的出现概率和不在生成树中的点的不出现的概率
于是现在的问题就是如何把概率给搞进去。不难发现如果我们把每条边的概率乘到M(G’)中,刚好可以满足树边那部分的概率,但非树边那部分还满足不了
于是再来考虑非树边,凑一凑发现:我们把p/(1-p)乘进去,全局再乘以(1-p)就可以满足条件了
所以L=M(G)*M(G)^T*p/(1-p)

所以直接把矩阵树定理的邻接矩阵的0/1变成概率就可以了
或者,更直接的理解:矩阵树定理里面的邻接矩阵可以推广到连边的个数,那应该可以推广到实数域,这样的话就可以对应概率了?

Code

1A辣,撒花~ ★,°:.☆( ̄▽ ̄)/$:.°★

#include<iostream>
#include<cstdio>
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int MAXN = 51;
const double EPS = 1e-8;

int n;
double G[MAXN][MAXN],rev=1;

inline double Gauss(){
	double ret = 1;
	for (int j=1,w=j;j<=n;w=++j) {
		for (int k=j+1;k<=n;k++) if (abs(G[j][k]) > abs(G[j][w])) w = k;
		if (w != j) {for (int i=1;i<=n;i++) swap(G[i][j],G[i][w]); ret *= -1;}
		for (int k=j+1;k<=n;k++) if (abs(G[j][k]) > EPS) {
			double t = G[j][k] / G[j][j];
			for (int i=1;i<=n;i++) G[i][k] -= G[i][j]*t;
		} ret *= G[j][j];
	} return ret;
}

int main(){
	scanf("%d",&n);
	for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) scanf("%lf",&G[i][j]), rev *= i<j?1:1-G[i][j];
	for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) G[i][j] = G[i][j]/(1-G[i][j])*-1;
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i != j) G[i][i] -= G[j][i];
	n--; printf("%.10lf\n",Gauss()*rev);
	return 0;
}

25 thoughts to “【BZOJ 3534】[Sdoi2014] 重建”

  1. Hello, i read your blog occasionally and i own a similar one and
    i was just curious if you get a lot of spam comments? If so how do you stop it, any
    plugin or anything you can recommend? I get so much lately it’s driving me insane
    so any help is very much appreciated.

  2. Hi, Neat post. There’s a problem together with your web site in internet explorer, could test this?
    IE nonetheless is the market chief and a good part of other folks will miss your wonderful writing due to this problem.

  3. With havin so much written content do you ever run into any problems of plagorism or copyright violation? My blog has a lot of unique
    content I’ve either authored myself or outsourced but it looks like a lot of it is popping it up all over the internet without my
    agreement. Do you know any ways to help prevent content from being ripped
    off? I’d really appreciate it.

  4. I think this is one of the most vital info for me. And i’m glad reading your article.
    But should remark on some general things, The web site style is perfect, the articles is really
    excellent : D. Good job, cheers

  5. Hi there, I found your web site via Google whilst looking for a
    related topic, your web site came up, it looks great. I’ve bookmarked it in my
    google bookmarks.
    Hello there, just was alert to your weblog through Google, and located that
    it is truly informative. I am going to be careful for brussels.
    I’ll be grateful in the event you continue this in future.
    A lot of other folks can be benefited out of your writing.
    Cheers!

  6. Yesterday, while I was at work, my cousin stole my iphone and tested to see if it
    can survive a 25 foot drop, just so she can be a
    youtube sensation. My iPad is now destroyed
    and she has 83 views. I know this is completely off topic but I had to share
    it with someone!

  7. This is really interesting, You are a very skilled blogger.
    I’ve joined your rss feed and look forward to seeking more of
    your fantastic post. Also, I’ve shared your site in my social networks!

  8. Hello! I’ve been following your site for some time now and finally got the courage to go ahead and give you a shout
    out from Huffman Texas! Just wanted to say keep up the excellent
    work!

  9. First off I would like to say great blog!

    I had a quick question that I’d like to ask if you do not mind.
    I was interested to know how you center yourself and clear your mind before writing.
    I have had a hard time clearing my thoughts in getting my ideas
    out there. I do enjoy writing but it just seems like the first 10 to 15 minutes are usually lost just
    trying to figure out how to begin. Any suggestions or tips?
    Kudos!

  10. I think this is one of the so much significant info for me.
    And i am satisfied studying your article. But want to
    remark on few common things, The web site style is wonderful, the articles
    is in point of fact nice : D. Excellent task, cheers

  11. Thank you, I have just been looking for information approximately this topic for a while and yours is the greatest I’ve discovered so far. However, what in regards to the bottom line? Are you sure in regards to the source?

  12. My family members all the time say that I am wasting my time here at net,
    except I know I am getting knowledge every day by reading thes
    pleasant posts.

  13. Do you mind if I quote a couple of your posts as long as
    I provide credit and sources back to your website? My blog is in the very same area of interest as yours
    and my visitors would certainly benefit from some of the information you present
    here. Please let me know if this ok with you. Regards!

  14. Undeniably believe that which you stated. Your favorite
    reason appeared to be on the internet the simplest thing to be aware of.

    I say to you, I definitely 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 effect , people could take a signal.

    Will probably be back to get more. Thanks

  15. Hi! This is my first comment here so I just wanted to give a quick
    shout out and tell you I truly enjoy reading your posts.
    Can you suggest any other blogs/websites/forums that deal with the same topics?
    Thanks for your time!

  16. My developer is trying to convince me to move to .net from PHP.

    I have always disliked the idea because of the
    expenses. But he’s tryiong none the less. I’ve been using Movable-type on numerous websites for
    about a year and am nervous about switching to another
    platform. I have heard good things about blogengine.net.
    Is there a way I can transfer all my wordpress posts into it?

    Any help would be really appreciated!

  17. Can I simply say what a relief to uncover somebody that actually knows what they are discussing on the internet.
    You definitely realize how to bring an issue to light and make
    it important. More people must look at this and understand this side of the story.

    I can’t believe you are not more popular since you surely have the
    gift.

  18. I’d must verify with you here. Which is not something I usually do! I enjoy studying a put up that may make individuals think. Additionally, thanks for allowing me to remark!

Leave a Reply to tinyurl.com Cancel reply

Your email address will not be published. Required fields are marked *