E.環(huán)的計(jì)數(shù)

1.到達(dá)i這個(gè)點(diǎn)有幾條路 ， 將方案數(shù)進(jìn)行傳遞

2.一個(gè)環(huán)中的起點(diǎn)可以是任意一個(gè)，是否需要記錄起點(diǎn)作為一個(gè)狀態(tài)，傳遞下去？

3.難點(diǎn)：從2可以想到，這個(gè)環(huán)中如果一定包含i這個(gè)點(diǎn)，則這個(gè)點(diǎn)一定可以作為起點(diǎn)。我們可以設(shè)置一個(gè)環(huán)中最值作為環(huán)中的起點(diǎn)？ 這樣就不用枚舉起點(diǎn)了，而且也不會(huì)算重。

4.復(fù)雜度2^191919是對(duì)的

5.坑點(diǎn)在于，需要考慮重復(fù)情況。第一，一個(gè)點(diǎn)作為起點(diǎn)之后統(tǒng)計(jì)出來(lái)的環(huán)，可以往左走，也可以往右走，因此算出來(lái)的方案數(shù)得除以2. 第二，兩個(gè)端點(diǎn)連接多條邊，會(huì)構(gòu)成雙元環(huán)，是我們統(tǒng)計(jì)的內(nèi)容。但是兩個(gè)點(diǎn)只有一條邊，也會(huì)被我們統(tǒng)計(jì)到，因此需要減掉.

#include <bits/stdc++.h>
#define int long long
#define N 2005
using namespace std;
int n, m, dp[1 << 19][20], g[20][20], ans, a, b;
int lowbit(int x) { return x & (-x); }
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        g[a][b] = g[b][a] = 1;
    }
    for (int i = 1; i <= n; i++) dp[1 << (i - 1)][i] = 1;
    for (int i = 1; i <= (1 << n) - 1; i++) {
        for (int j = 1; j <= n; j++) {  // j是以誰(shuí)結(jié)尾
            if (dp[i][j] == 0)
                continue;
            if ((1 << (j - 1) & i) == 0)
                continue;
            for (int k = 1; k <= n; k++) {
                if (g[j][k] == 0 || lowbit(i) > 1 << (k - 1))
                    continue;
                if ((1 << (k - 1) & i) == 0)  //未到的點(diǎn)
                    dp[i | (1 << (k - 1))][k] += dp[i][j];
                else if ((1 << (k - 1)) == lowbit(i))  //已有的點(diǎn)
                    ans += dp[i][j];
            }
        }
    }
    ans -= m;
    cout << ans / 2 << endl;
    return 0;
}

F.寶藏
1.比較容易分析出來(lái)，最終的形態(tài)一定是一棵樹(shù)。每一個(gè)節(jié)點(diǎn)v一定有一個(gè)父親u，答案是$w(u,v) \times $樹(shù)的深度
2.我們可以枚舉樹(shù)當(dāng)前這一層中有哪些節(jié)點(diǎn)，和上一層的節(jié)點(diǎn)相連接選擇其中最小的邊值。但是復(fù)雜度不對(duì)。
3.這里有個(gè)trick：當(dāng)求解的答案更大時(shí)，對(duì)最終的最優(yōu)解沒(méi)有影響，因此我可以不枚舉前一層到底有哪些點(diǎn)，之前的所有點(diǎn)集都枚舉一遍，最優(yōu)解不受影響。
因此，枚舉子集作為當(dāng)前層的點(diǎn)集k，前i層的狀態(tài)j,j^i為前i-1層的狀態(tài)。求最小權(quán)值之和?當(dāng)前層的樹(shù)深度。
3.復(fù)雜度:枚舉樹(shù)的深度，枚舉前i層的狀態(tài)，枚舉子集作為當(dāng)前層的集合，3^n?n + 預(yù)處理3^n ? n ? n = 3^12 × 12 × 12 = 76,527,504

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int M=(1<<12),inf=0x3f3f3f3f;
int cost[M][M],n,m,c[12][12];
long long dp[12][M],ans=inf;
void init(){
	for(int i=1;i<(1<<n);i++){//i當(dāng)前及前面所有點(diǎn)構(gòu)成的集合
		for(int j=i;j;j=(j-1)&i){//j當(dāng)前這層的點(diǎn)構(gòu)成的集合
			if(j==i)continue;
			for(int t=0,tmp;t<n;t++,tmp=inf){
				if(!(((i^j)>>t)&1))continue;//t是不包括當(dāng)前層的點(diǎn)
				for(int l=0;l<n;l++)if((j>>l)&1)tmp=min(tmp,c[l][t]);//l當(dāng)前這層的點(diǎn)
				if(tmp>=inf){cost[j][i]=inf;break;}
                else cost[j][i]+=tmp;//j當(dāng)前層的集合，當(dāng)前層及前面所有層的點(diǎn)的集合
			}
		}
	}
	return;
}
long long DP(int x){
    for(int i=0;i<12;i++)for(int j=0;j<M;j++)dp[i][j]=inf;//dp值取min,所以先清空
	dp[0][1<<x]=0;
	long long res=inf;
	for(int i=1;i<n;i++){
		for(int j=1;j<(1<<n);j++){
			for(int k=j;k;k=(k-1)&j){//當(dāng)前i層的狀態(tài)k,前i層的狀態(tài)j,構(gòu)成的花費(fèi)cost[k][j]
				if(k==j)continue;
				dp[i][j]=min(dp[i][j],dp[i-1][k]+1ll*i*cost[k][j]);
			}
			if(j==(1<<n)-1)res=min(res,dp[i][j]);
		}
	}
	return res;
}
int main(){
	scanf("%d %d",&n,&m);
	if(n==1){
		printf("0\n");
		return 0;
	}
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)c[i][j]=inf;
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d %d %d",&u,&v,&w),u--,v--;
		c[v][u]=c[u][v]=min(c[u][v],w);
	}
	init();
	for(int i=0;i<n;i++)ans=min(ans,DP(i));
	printf("%lld\n",ans);
	return 0;
}