矩阵树定理 学习笔记

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define lon long long
using namespace std;
const int n7=303;const lon mo=1000000007;
int n,m,sys;lon a[n7][n7],ans=1;

void edge(int sta,int edn,int w){
	a[edn][edn]=(a[edn][edn]+w)%mo,a[edn][sta]=(a[edn][sta]-w+mo)%mo;
}

int rd(){
	int shu=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))shu=(shu<<1)+(shu<<3)+ch-'0',ch=getchar();
	return shu;
}

void Dswap(int N,int p,int q){
	rep(i,1,N)swap(a[p][i],a[q][i]);
}
 
void deter(int N){
	bool fu=0;
	rep(i,1,N){
		int wei=i;bool flag=0;
		rep(j,i,N){
			if(a[j][i]&&!flag)flag=1;
			if(a[j][i]&&a[j][i]<a[wei][i])wei=j;
		}
		if(!flag){ans=0;return;}
		if(i!=wei)Dswap(N,i,wei),fu=1-fu;
		rep(j,i+1,N){
			if(a[j][i]>a[i][i]){Dswap(N,i,j);fu=1-fu;}
			while(a[j][i]){
				lon tmp=a[i][i]/a[j][i];
				rep(k,i,N)a[i][k]=(a[i][k]+(mo-tmp)*a[j][k])%mo;				
				Dswap(N,i,j);
				fu=1-fu;
			}
		}
		ans=ans*a[i][i]%mo;
	}
	if(fu)ans=(-ans+mo)%mo;
}

int main(){
	n=rd(),m=rd(),sys=rd(); 
	rep(i,1,m){
		int sta=rd(),edn=rd(),w=rd();
		if(sta==edn)continue;
		edge(sta,edn,w);
		if(!sys)edge(edn,sta,w);
	}
	rep(i,1,n)rep(j,1,n)a[i][j]=a[i+1][j+1];
	deter(n-1);
	printf("%lld",ans);
	return 0;
}