Brief description :

生成树计数问题；求一个给定一个包含 n 个结点的无向图生成树的数目。
（1 <= n <= 12 ...）

Analyse :

。。补完了前回两个回路问题的轮廓线算法，（之前完全是按照自己臆想设计了一个和脑海里已有印象差别不大的。。）这样说着，应该说轮廓线是分析一类问题的思路，称作完全不同的算法并不恰当，它们在讨论的阶段也完全一致，不过比较一番也有必要。

不过学习一下这种用两张散列滚动递推的写法还是很好啊啊。@（…後者 Formular 一题相较开始明显，逐行推 0.640+ms，轮廓线 0.040+ms，啊暂时不讨论这些了… ）

对于这题，无误的话应可状态压缩，考虑每个点是否在当前的生成树中，之後…
发现不行（会出现重复计数），进一步细化，对每个点进行黑、白、灰染色，如同 Prim 算法进行时那样。那么递推的过程，每轮取出所有灰色点，并通过一次DFS进行状态转移。时间复杂度为 $$O(3^n n^2)$$。

#include 
#include 
#include 
using namespace std;
const int nn = 12, ss = 531441;
const int P[nn + 1] = {1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441};
const int WHITE = 0, GRAY = 1, BLACK = 2;
int A[ss][nn], D[nn]; bool G[nn][nn];
int n, m; long long ans, d;


struct hashTable{
	int state[ss], pos[ss], sz;
	long long key[ss];
	
	inline void clear(){
		sz = 0;
		memset(pos, -1, sizeof(pos));
	}
	inline bool empty(){
		return sz == 0;
	}
	inline void insert(int s){
		if ( pos[s] != -1 ) {
			key[pos[s]] += d;
			return;
		}
		state[sz] = s, key[sz] = d;
		pos[s] = sz++;
	}
} H[2] , *src , *des;

void dfs(int s, int i){
	if (i==n){
		des->insert(s);
	}
	else {
		if (D[i]!=0){
			d *= D[i], dfs(s+P[i], i+1), d /= D[i];
		}
		dfs(s, i+1);
	}
}


int main(){
	
	//freopen("in.txt", "r", stdin);
	
	for (int i = 1; i < ss; i ++){
		for (int j = 0, s = i; j < nn && s != 0; j ++)
			A[i][j] = s % 3, s /= 3;
	}
	
	int flag;
	int T; cin >> T;
	while (T--){
		memset(G, false, sizeof(G));
		cin >> n >> m;
		int x, y;
		for (int i=0;iinsert(1);
		
		while (!des->empty()){
			swap(src, des), des->clear();
			for (int it = 0; it < src->sz; it ++){
				int s = src->state[it], d = src->key[it];
				//cout << s << " " << d << endl;
				memset(D, 0, sizeof(D));
				flag = BLACK;
				
				for (int i = 0; i < n; i ++)
					if (A[s][i]==GRAY){
						for (int j = 0; j < n; j ++)
							if (A[s][j] == WHITE && G[i][j]) D[j] ++, flag = GRAY;
						s += P[i];
					}
					else{
						if (flag == BLACK && A[s][i] == WHITE) flag = WHITE;
					}
				
				
				if (flag==GRAY) dfs(s, 0);
				else if (flag==BLACK) ans += d;
			}
			
			//cout << "------" << endl;
			
			
		}
		
		cout << ans << endl;	
	}
	
}

居然超时了。。。只好用 Kirchhoff 矩阵了。。

#include 
#include 
#include 
using namespace std;
const double ESP = 1e-15;
const int nn = 12;
double K[nn][nn]; int A[nn][nn], D[nn][nn];
int n, m; 

bool isZero(double x){
	return (-ESP <= x && x <= ESP);
}

double det(){
	double key, det = 1;
	int i, j, k;
	for (i=0;i> T;
	while (T--){
		memset(A, 0, sizeof(A));
		memset(D, 0, sizeof(D));
		cin >> n >> m;
		
		int x, y;
		for (int i=0;i



External link :
https://www.spoj.pl/problems/HIGH/
                                                												

													Posted by 
													xiaodao													
													Category: 													日常