【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;
}

【BZOJ 4031】[HEOI2015] 小Z的房间

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4031

仍然是裸的矩阵树

#include<iostream>
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const LL MAXN = 100;
const LL MOD = 1000000000;

LL G[MAXN][MAXN],n,m,num[MAXN][MAXN],cnt;
char pat[MAXN];

inline int Gauss(){
	for (LL j=1;j<=n;j++) for (LL i=1;i<=n;i++) 
		G[i][j] = (G[i][j]%MOD + MOD) % MOD;
	LL ret = 1;
	for (LL j=1;j<=n;j++) {
		for (LL k=j+1;k<=n;k++) while (G[j][k]) {
			LL t = G[j][j] / G[j][k];
			for (LL i=1;i<=n;i++) G[i][j] = ((G[i][j] - G[i][k]*t) % MOD + MOD) % MOD;
			for (LL i=1;i<=n;i++) swap(G[i][j], G[i][k]); ret *= -1; ret = (ret%MOD + MOD) % MOD;
		} 
		ret = (G[j][j]*ret%MOD + MOD) % MOD;
	} return ret; 
}

inline void AddEdge(LL u, LL v){
	G[u][u]++; G[v][v]++; 
	G[u][v]--; G[v][u]--;
}

int main(){
	scanf("%d%d",&m,&n);
	for (LL j=1;j<=m;j++) {
		scanf("%s",pat+1);
		for (LL i=1;i<=n;i++) if (pat[i] == '.') {
			num[i][j] = ++cnt;
			if (num[i-1][j]) AddEdge(num[i][j],num[i-1][j]);
			if (num[i][j-1]) AddEdge(num[i][j],num[i][j-1]);
		}
	} n = cnt-1; printf("%d\n",Gauss());
	return 0;
}

【BZOJ 2467】[中山市选2010] 生成树

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2467

传说中的矩阵树定理!其实搞一搞排列组合,然后O(1)输出就可以了QAQ
唯一值得一提的,就是高斯消元那里,因为有除,且模数不是质数(不一定有逆元)
所以只能使用类似辗转相除的方法,而不能搞LCM

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 400+9;
const int MOD = 2007;

int G[MAXN][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 int id(int i, int j){
	if (i>n) i -= n;
	return (--i)*4+j;
}

inline void Add_Edge(int u, int v){
	G[u][u]++; G[v][v]++;
	G[u][v]--; G[v][u]--;
}

inline void Build_Matrix(){
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=3;j++) Add_Edge(id(i,j),id(i,j+1));
		Add_Edge(id(i,4),id(i+1,1)); Add_Edge(id(i,1),id(i+1,1));
	}n *= 4; n--;
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) G[i][j] = (G[i][j]%MOD + MOD) % MOD;
}

inline int Gauss(){
	int ret = 1;
	for (int j=1,w=0;j<=n;j++) {
		for (int k=j+1;k<=n;k++) while (G[j][k]) {
			int t = G[j][j]?G[j][k] / G[j][j]:1;
			for (int i=1;i<=n;i++) G[i][k] = ((G[i][k] - G[i][j]*t) % MOD + MOD) % MOD;
			for (int i=1;i<=n;i++) swap(G[i][k], G[i][j]); ret *= -1;
		} ret = ret*G[j][j] % MOD;
	} return (ret + MOD) % MOD;
}

int main(){
	for (int T=read();T;T--) {
		n = read(); memset(G,0,sizeof(G));
		Build_Matrix(); 
		printf("%d\n",Gauss());
	}
	return 0;	
}