bzoj5297: [Cqoi2018]社交网络

学了个新东西：矩阵树定理。就是生成树计数嘛。（听说cqoi2018都是裸题？？）

构出基尔霍夫矩阵，论文是无向图，有向图的话度数矩阵应该是入度，邻接矩阵连单向边

求出矩阵行列式即可（好像这东西scy初一教过，没什么印象了囧）

不是任意n-1阶主子式吗。。。我把第1行第1列删了就过了，第n行第n列删了就过不去。。。还是说我哪里写挫了。。。

-------upd--------------

ORZ肉老师%%%%%%因为是有向图所以要删掉的必须是根那一行

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int mod=10007;
int MOD(int x){return (x%mod+mod)%mod;}

int n,kf[310][310];
int gethls()
{
    int ans=1,tp=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int x=i,y=j;  
            while(kf[y][i]!=0)  
            {  
                int t=kf[x][i]/kf[y][i];
                for(int k=i;k<=n;k++)  
                    kf[x][k]=MOD(kf[x][k]-kf[y][k]*t);  
  
                swap(x,y);  
            }  
            if(x!=i)
            {  
                for(int k=2;k<=n;k++)  
                    swap(kf[i][k],kf[x][k]);  
                tp=0-tp;
            }
        }
        ans=MOD(ans*kf[i][i]);
    }
    ans=MOD(ans*tp);
    return ans;
}
int main()
{
    int m,x,y;
    scanf("%d%d",&n,&m);
    memset(kf,0,sizeof(kf));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        kf[x][x]++;
        kf[y][x]--;
    }
    for(int i=2;i<=n;i++)
        for(int j=2;j<=n;j++)kf[i][j]=MOD(kf[i][j]);
    printf("%d
",gethls());
    return 0;
}