NOIP2017 宝藏

$$ f\left( vtx,len,set \right) \text{表示当前在点}vtx\text{，已经挖了长度为}len\text{的道路，要去挖通}set\text{这些点的最小代价} \\ \text{转移：} \\ \text{对于每一个}vtx\text{，枚举出边，对于每一个出边}\left( vtx,to \right) \text{，枚举要从这个点去挖的子集}\left( \text{这个子集必须要包含}to \right) \text{，然后统计上挖这条边的代价。} \\ \\ f\left( vtx,len,set \right) =MIN_{S\subset \ set\ and\ vtx\ \notin \ S}MIN_{edge\ \left( vtx,to \right) \ and\ to\in \ S}f\left( to,len+\text{1,}S \right) \ +\ f\left( vtx,len,S^{set} \right) \ +\left( len+1 \right) \times weight\left( vtx,to \right) \ \\ \text{边界条件:} \\ f\left( vtx,len,0 \right) =0 \\ \text{挖空集的代价为}0 \\ $$

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <string>
typedef  int int_t;

using std::cin;
using std::endl;
using std::cout;

const int_t LARGE = 20;
const int_t INF = 0x3f3f3f3f;


int_t n,m;

int_t graph[LARGE + 1][LARGE + 1];
int_t memory[LARGE + 1][LARGE + 1][1 << 13];
bool visited[LARGE + 1][LARGE + 1][1 << 13];
int_t* subsets[1 << 13];
struct Edge{
    int_t to;
    int_t weight;
    int_t next;
    Edge(int_t to = 0,int_t weight = 0,int_t next = 0){
        this -> to = to;
        this -> weight = weight;
        this -> next = next;
    }
} edges[LARGE * LARGE + 1];
int_t next = 1;
int_t head[LARGE + 1];
void pushEdge(int_t from,int_t to,int_t weight){
    int_t id = next++;
    edges[id] = Edge(to,weight,head[from]);
    head[from] = id;
}

int_t search(int_t vtx,int_t len,int_t set) {
	//要去挖空集
	if(set == 0) return memory[vtx][len][set] = 0;
	//已经挖了长度为n - 1的链
	if(len == n - 1) {
		if(set != 0) return memory[vtx][len][set] = INF;
	}
	int_t& result = memory[vtx][len][set];
	if(visited[vtx][len][set]) return result;
	visited[vtx][len][set] = true;
	//不要把结果在记忆化返回前赋值 
	result = INF;
	for(int_t ptr = head[vtx];ptr != 0; ptr = edges[ptr].next) {
	    int_t to = edges[ptr].to;
	    int_t weight = edges[ptr].weight;
		//枚举出边
		if(to == vtx  || (set & (1 << to)) == 0) continue;
		//枚举要挖的子集
		//不能去挖空集
		for(int_t k = 1; k <= subsets[set][0]; k ++) {
			int_t x = subsets[set][k];
			if(x & (1 << to)) {
				result = std::min(result,search(to , len + 1, x & (~(1 << to))) + weight * (len + 1) + search(vtx,len,set & (~(x))));
			}
		}
	}
	return result;
}

int main() {
	cin >> n >> m;
	for(int_t i = 0; i < n; i++) {
		for(int_t j = 0; j < n; j++) {
			graph[i][j] = INF;
		}
	}
	for(int_t i = 1; i <= m; i ++) {
		int_t from,to,weight;
		cin >> from >> to >> weight;
		from -= 1;
		to -= 1;
		graph[from][to] = std::min(graph[from][to],weight);
		graph[to][from] = graph[from][to];
	}
	for(int_t i = 0;i < n;i++){
	    for(int_t j = 0;j < n;j++){
	        if(graph[i][j] < INF && i != j){
	            pushEdge(i,j,graph[i][j]);
            }
        }
    }
    static int_t subset[1 << 13];
    for(int_t i = 1 ;i < (1 << n);i ++){
        
        for(int_t j = 1;j <= i;j++){
            if((j & i) == j) subset[++subset[0]] = j;
        }
        std::sort(subset + 1,subset + 1 + subset[0]);
        int_t* tail = std::unique(subset + 1,subset + 1 + subset[0]);
        subsets[i] = new int_t[tail - subset];
        memcpy(subsets[i],subset,sizeof(int_t) * (tail - subset));
        subset[0] = 0;
    }
	int_t result = INF;
	for(int_t i = 0; i < n; i++) {
	    int_t temp = search(i,0,((1 << n) - 1) ^ (1 << i));
		result = std::min(result,temp);
	}
	cout << result << endl;
	return 0;
}