UvaLive 6600 Spanning trees in a secure lock pattern 矩陣行列式
來(lái)源：程序員人生 發(fā)布時(shí)間：2014-09-01 23:59:24 閱讀次數(shù)：2731次
鏈接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4611
題意：給一個(gè)N*N個(gè)點(diǎn)的矩陣(N<=6)，每個(gè)點(diǎn)只能和周?chē)藗€(gè)點(diǎn)相連，問(wèn)有多少種生成樹(shù)的方式。
思路：題里給的很明白，就是列一個(gè)每個(gè)點(diǎn)的邊的矩陣，然后求子矩陣的行列式就可以了，因?yàn)镹只有6，所以打表就可以了。
打表代碼：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
#define MOD 1000
#define maxn 40
#define maxm 40
struct Matrix
{
int n,m;
double a[maxn][maxm];
void change(int c,int d)
{
n=c;
m=d;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
a[i][j]=0;
}
void Copy(const Matrix &x)
{
n=x.n;
m=x.m;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
a[i][j]=x.a[i][j];
}
void build(int n)
{
change(n*n,n*n);
for(int i=0; i<n*n; i++)
{
if(i%n!=0)
{
a[i][i-1]=-1;
a[i-1][i]=-1;
a[i][i]++;
a[i-1][i-1]++;
}
if(i%n!=0&&i/n!=0)
{
a[i][i-n-1]=-1;
a[i-n-1][i]=-1;
a[i][i]++;
a[i-n-1][i-n-1]++;
}
if(i%n!=0&&i/n!=n-1)
{
a[i][i+n-1]=-1;
a[i+n-1][i]=-1;
a[i][i]++;
a[i+n-1][i+n-1]++;
}
if(i/n!=n-1)
{
a[i][i+n]=-1;
a[i+n][i]=-1;
a[i][i]++;
a[i+n][i+n]++;
}
}
}
double det()
{
for(int i=1; i<n; i++)
{
for(int j=0; j<i; j++)
if(a[i][j]!=0)
{
for(int k=j+1; k<m; k++)
a[i][k]-=(a[j][k]*a[i][j]/a[j][j]);
a[i][j]=0;
}
}
double ans=1;
for(int i=0; i<n-1; i++)
ans*=a[i][i];
return ans;
}
};
int main()
{
int t;
scanf("%d",&t);
Matrix A;
A.build(t);
printf("%.0f
",A.det());
return 0;
}
AC代碼：
int main()
{
char ss[10][40]={"1","16","17745","1064918960","3271331573452806","504061943351319050000000"};
int T;
scanf("%d",&T);
while(T--)
{
int a;
scanf("%d",&a);
puts(ss[a-1]);
}
}
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
