沈阳什么行业做网站的最多,南宁市建设信息网站,创网网站后台管理系统,ASP net网站开发资料正题
题目链接:https://www.luogu.com.cn/problem/P6178 题目大意
给出一个nnn个点mmm条边的无向/有向图。
求所有的生成树/以1为根的外向生成树的权值乘积和。 解题思路
矩阵AAA的行列式表示为det(A)det(A)det(A)#xff0c;定义为 det(A)∑P(−1)μ(P)∏i1nAi,pidet(A)\…正题
题目链接:https://www.luogu.com.cn/problem/P6178 题目大意
给出一个nnn个点mmm条边的无向/有向图。
求所有的生成树/以1为根的外向生成树的权值乘积和。 解题思路
矩阵AAA的行列式表示为det(A)det(A)det(A)定义为 det(A)∑P(−1)μ(P)∏i1nAi,pidet(A)\sum_P(-1)^{\mu(P)}\prod_{i1}^nA_{i,p_i}det(A)P∑(−1)μ(P)i1∏nAi,pi 其中PPP是一个1∼n1\sim n1∼n的排列μ(P)\mu(P)μ(P)表示排列PPP的逆序对数量
即每一行选择一个数乘起来容斥系数与排列逆序对数量有关
我们需要解决的问题是如何快速求出一个矩阵的行列式考虑如果对于所有行iii都满足i1∼ni1\sim ni1∼n都没有值那么此时有det(A)∏i1nAi,idet(A)\prod_{i1}^nA_{i,i}det(A)∏i1nAi,i。这个很容易理解因为如果一行选择的不是iii那么一定存在有一行jjj的选择大于jjj那么此时这个方案的权值就为000了。
那么我们需要将一个矩阵变换成一个行列式不变的上三角矩阵这里需要用到行列式的初等变换
若交换两行那么行列式。因为交换后原来权值相同的容斥系数都会变化所以值取反。[ax,byc,d][a,bc,d][x,yc,d]\begin{bmatrix}ax,by\\c,d\end{bmatrix}\begin{bmatrix}a,b\\c,d\end{bmatrix}\begin{bmatrix}x,y\\c,d\end{bmatrix}[ax,byc,d][a,bc,d][x,yc,d]乘法分配率可得若有两行完全相同那么这个行列式为000。证明方法是交换这两行后矩阵不变理论上行列式也不便但是行列式取反了也就是原行列式为000若让一行加上另一行那么行列式不变证明的话[a,ba,b]0\begin{bmatrix}a,b\\a,b\end{bmatrix}0[a,ba,b]0 [a,bac,bd][a,ba,b][a,bc,d][a,bc,d]\begin{bmatrix}a,b\\ac,bd\end{bmatrix}\begin{bmatrix}a,b\\a,b\end{bmatrix}\begin{bmatrix}a,b\\c,d\end{bmatrix}\begin{bmatrix}a,b\\c,d\end{bmatrix}[a,bac,bd][a,ba,b][a,bc,d][a,bc,d]
然后这样就可以用高斯消元的方法消矩阵了然后就可以求出行列式了。
回到这题来矩阵树定理大体来说就是AAA表示一张无向图的邻接矩阵DDD表示度数矩阵Di,iD_{i,i}Di,i为iii的度数其他为000。去掉DDD和AAA的第kkk行和第kkk列之后就有det(D−A)det(D-A)det(D−A)就表示这张图的生成树个数。
当然有向图也可以如果是外向树那么DDD表示入度矩阵内向就是出度矩阵若xxx为根去掉第xxx行第xxx列之后det(D−A)det(D-A)det(D−A)就是答案了。
这里是求权值乘积和重边数等于权值就好了。
时间复杂度O(n3)O(n^3)O(n3) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N310,P1e97;
ll n,m,t,ans,a[N][N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void dec(){ll f1;ans1;for(ll i2;in;i){ll wi;for(ll ji;jn;j)if(a[i][j]){if(i!j)f-f;wj;break;}swap(a[i],a[w]);ll invpower(a[i][i],P-2);ansans*a[i][i]%P;if(!a[i][i])return;for(ll ji;jn;j)a[i][j]a[i][j]*inv%P;for(ll ji1;jn;j){ll rateP-a[j][i];for(ll ki;kn;k)a[j][k](a[j][k]rate*a[i][k]%PP)%P;}}ansans*f;return;
}
int main()
{scanf(%lld%lld%lld,n,m,t);for(ll i1;im;i){ll x,y,w;scanf(%lld%lld%lld,x,y,w);if(t)a[y][y](a[y][y]w)%P,a[x][y](a[x][y]-w)%P;else a[x][x](a[x][x]w)%P,a[y][y](a[y][y]w)%P,a[x][y](a[x][y]-w)%P,a[y][x](a[y][x]-w)%P;}dec();printf(%lld\n,(ansP)%P);
}
