求助矩阵树定理的删去任意行列....
查看原帖
求助矩阵树定理的删去任意行列....
299810
issue_is_fw楼主2020/11/5 11:04

求助...不是说删去任意对应行列结果一样嘛...

第一个代码上去第一行第一列就过了

第二个代码删去第n行第n列就错了....

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 609;
const int mod = 1e9+7;
int a[maxn][maxn],n,m,t,ans=1;
void guass()
{
	for(int i=2;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)	
			if( a[j][i]>a[i][i] ){swap( a[i],a[j] ); ans=-ans; break; }
		for(int j=i+1;j<=n;j++)
		{
			while( a[j][i] )
			{
				int d = a[i][i]/a[j][i];
				for(int k=i;k<=n;k++)
					a[i][k] = (a[i][k]-a[j][k]*d%mod )%mod;
				swap(a[i],a[j]);
				ans = -ans;
			}
		}
	}
}
signed main()
{
	cin >> n >> m >> t;
	for(int i=1;i<=m;i++)
	{
		int x,y,w; scanf("%lld%lld%lld",&x,&y,&w);
		if( t==0 )
		{
			a[x][x] = ( a[x][x]+w )%mod, a[y][y] = ( a[y][y]+w )%mod;
			a[x][y] = ( a[x][y]-w )%mod, a[y][x] = ( a[y][x]-w )%mod;
		}
		else
		{
			a[y][y] = ( a[y][y]+w )%mod;
			a[x][y] = ( a[x][y]-w )%mod;
		}
	}
	guass();
	for(int i=2;i<=n;i++)
		ans = ans*a[i][i]%mod;
	cout << ( ans%mod+mod )%mod;
}

错误的代码就改了下删去的行列...

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 609;
const int mod = 1e9+7;
int a[maxn][maxn],n,m,t,ans=1;
void guass()
{
	for(int i=1;i<n;i++)
	{
		for(int j=i+1;j<n;j++)	
			if( a[j][i]>a[i][i] ){swap( a[i],a[j] ); ans=-ans; break; }
		for(int j=i+1;j<n;j++)
		{
			while( a[j][i] )
			{
				int d = a[i][i]/a[j][i];
				for(int k=i;k<n;k++)
					a[i][k] = (a[i][k]-a[j][k]*d%mod )%mod;
				swap(a[i],a[j]);
				ans = -ans;
			}
		}
	}
}
signed main()
{
	cin >> n >> m >> t;
	for(int i=1;i<=m;i++)
	{
		int x,y,w; scanf("%lld%lld%lld",&x,&y,&w);
		if( t==0 )
		{
			a[x][x] = ( a[x][x]+w )%mod, a[y][y] = ( a[y][y]+w )%mod;
			a[x][y] = ( a[x][y]-w )%mod, a[y][x] = ( a[y][x]-w )%mod;
		}
		else
		{
			a[y][y] = ( a[y][y]+w )%mod;
			a[x][y] = ( a[x][y]-w )%mod;
		}
	}
	guass();
	for(int i=1;i<n;i++)
		ans = ans*a[i][i]%mod;
	cout << ( ans%mod+mod )%mod;
}
2020/11/5 11:04
加载中...