jzoj 5899. 【NOIP2018模拟10.6】资源运输 矩阵树定理
Description
Input
Output
Sample Input
3 2
1 3 5
2 1 6
Sample Output
30
样例说明:
显然m=n-1时,只有一种选择方法,优秀程度为5*6=30,所以输出为30。
Data Constraint
分析:
答案就是每棵生成树的价值和除以生成树的数量。
因为价值的边的权值,所以都可以直接用矩阵树解决。
代码:
#include <iostream>
#include <cstdio>
#include <cmath>
#define LL long long
const int maxn=307;
const LL mod=998244353;
using namespace std;
LL n,m,x,y,w;
LL a[maxn][maxn],b[maxn][maxn];
LL power(LL x,LL y)
{
if (y==1) return x;
LL c=power(x,y/2);
c=(c*c)%mod;
if (y%2) c=(c*x)%mod;
return c;
}
LL det()
{
LL ans=1;
for (int i=1;i<=n;i++)
{
LL inv=power(a[i][i],mod-2);
for (int j=i+1;j<=n;j++)
{
LL rate=a[j][i]*inv%mod;
for (int k=i;k<=n;k++)
{
a[j][k]=(a[j][k]+mod-rate*a[i][k]%mod)%mod;
}
}
ans=(ans*a[i][i])%mod;
}
return ans;
}
int main()
{
freopen("avg.in","r",stdin);
freopen("avg.out","w",stdout);
scanf("%lld%lld",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&x,&y,&w);
a[x][y]=mod-1;
a[y][x]=mod-1;
a[x][x]++;
a[y][y]++;
b[x][y]=mod-w;
b[y][x]=mod-w;
b[x][x]=(b[x][x]+w)%mod;
b[y][y]=(b[y][y]+w)%mod;
}
n--;
LL B=det();
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++) a[i][j]=b[i][j];
}
LL A=det();
printf("%lld",A*power(B,mod-2)%mod);
}