BZOJ5297 [CQOI2018] 交互网络【MatrixTree定理】

题目分析：

　　这题是一道板题，属于MatrixTree定理的简单拓展，邻接矩阵与有向图邻接矩阵一致，度数矩阵作为入度矩阵。然后高斯消元即可。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int mod = 10007;
 5 
 6 int n,m,ans;
 7 int g[300][300];
 8 int dr[300][300];
 9 
10 void read(){
11     scanf("%d%d",&n,&m);
12     for(int i=1;i<=m;i++){
13     int u,v; scanf("%d%d",&u,&v);
14     g[v][u]++;
15     dr[u][u]++;
16     }
17 }
18 
19 void BuildMatrix(){
20     for(int i=1;i<=n;i++)
21     for(int j=1;j<=n;j++)dr[i][j]=(dr[i][j]-g[i][j]+mod)%mod;
22 }
23 
24 int fast_pow(int now,int p){
25     int nowp = now,ans = 1,mov = 1;
26     while(mov <= p){
27     if(mov & p){ans = (1ll*ans*nowp)%mod;}
28     mov<<=1,nowp = (1ll*nowp*nowp)%mod;
29     }
30     return ans;
31 }
32 
33 void Gauss(){
34     int pp = 1;
35     for(int i=2;i<n;i++){
36     int im = 0;
37     for(int j=i;j<=n;j++){
38         if(dr[j][i]) im = j;
39     }
40     if(!im) return;
41     if(im != i){pp*=-1;for(int j=i;j<=n;j++) swap(dr[i][j],dr[im][j]);}
42     for(int j=i+1;j<=n;j++){
43         int bl = (dr[j][i]*fast_pow(dr[i][i],mod-2))%mod;
44         for(int k=i;k<=n;k++){
45         dr[j][k] -= bl*dr[i][k];
46         dr[j][k] %= mod;dr[j][k] += mod; dr[j][k] %=mod;
47         }
48     }
49     }
50     ans = 1;
51     for(int i=2;i<=n;i++){
52     ans = (ans*dr[i][i])%mod;
53     }
54     if(pp == -1){ans = mod-ans;}
55 }
56 
57 void work(){
58     BuildMatrix();
59     Gauss();
60     printf("%d",ans);
61 }
62 
63 int main(){
64     read();
65     work();
66     return 0;
67 }

BZOJ5297 [CQOI2018] 交互网络 【MatrixTree定理】

BZOJ5297 [CQOI2018] 交互网络【MatrixTree定理】