HDU 4085 Peach Blossom Spring 记忆化搜索枚举子集 斯坦纳树

题目链接：点击打开链接

题意:

第一行输入n个点 m条可修建的无向边 k个人

下面给出修建的边和修建该边的花费。

开始时k个人在1-k的每个点上（一个点各一人）

目标:从m条给定边中修建部分边使得花费和最小

让k个人移动到 [n-k+1, n] 后面的k个点上（每个点放一个人）。

思路:

首先就是一道斯坦纳树，还是先求一个dp数组（求解方法：点击打开链接）

dp[i][j] 表示以i为根 ，j为8个点中是否在 i 的子树里 时的最小花费。

现在的问题就是如何求答案。

因为一个人到他的目标点这条路径可能和别人的不连通，也就是多个最小生成树，

我们枚举2*k个点哪些点是在一个连通分量里的，

则对于状态x中，表示人的二进制是低k位，表示目标点的是高k位，x中1表示这些点是在一个连通分量里的，

对于这个x的最小花费就是min( dp[ anypoint regard root ][x])

而x必须保证低k位中1的个数 和高k位中1的个数相同（即人数和目标点个数相同）

然后记忆化搜索即可。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
template <class T>
inline bool rd(T &ret) {
    char c; int sgn;
    if (c = getchar(), c == EOF) return 0;
    while (c != '-' && (c<'0' || c>'9')) c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return 1;
}
template <class T>
inline void pt(T x) {
    if (x <0) {
        putchar('-');
        x = -x;
    }
    if (x>9) pt(x / 10);
    putchar(x % 10 + '0');
}
int Pow(int x, int y) {
    int ans = 1;
    while (y > 0) {
        if ((y & 1) > 0)
            ans *= x;
        y >>= 1;
        x = x * x;
    }
    return ans;
}
using namespace std;
const int inf = 1e8;
const int N = 55;
const int M = 500010;
int n, m, k, ans;
int dis[N][N], dp[N][1 << 10];
int e[10];
int vis[N];
int mem[1 << 10];
int check(int x){
    int a = 0, b = 0;
    for (int i = 0; i < k; i++)
    if ((x&(1 << i))>0)a++;
    for (int i = 0; i < k; i++)
    if ((x&(1 << (i + k)))>0)b++;
    if (a != b)return -1;
    int ans = inf;
    for (int i = 0; i < n; i++)
        ans = min(ans, dp[i][x]);
    return ans;
}
int dfs(int x){
    if (mem[x] != -1)return mem[x];
    int tmp = check(x);
    if (tmp == -1)return mem[x] = inf;
    int ans = tmp;
    for (int i = (x-1)&x; i > 0; i = (i - 1)&x){
        ans = min(ans, dfs(i) + dfs(x - i));
    }
    return mem[x] = ans;
}
void floyd(){
    for (int z = 0; z < n; z++)
    for (int j = 0; j < n; j++)
    for (int i = 0; i < n; i++)
        dis[i][j] = min(dis[i][j], dis[j][z] + dis[z][i]);
}
void input(){
    rd(n); rd(m); rd(k);
    for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)dis[i][j] = (i==j)?0:inf;
    int u, v, d;
    while (m-->0){
        rd(u); rd(v); rd(d); 
        u--; v--;
        dis[u][v] = dis[v][u] = min(dis[u][v], d);
    }
    for (int z = 0; z < n; z++)
    for (int j = 0; j < n; j++)
    for (int i = 0; i < n; i++)
        dis[i][j] = min(dis[i][j], dis[j][z] + dis[z][i]);
}
int main(){
    int T; rd(T);
    while (T-->0){
        input();
        floyd();
        for (int i = 0; i < k; i++)e[i] = i; for (int i = 0; i < k; i++)e[i + k] = n - k + i;
        for (int i = 0; i < n; i++)for (int j = 0; j < (1 << (2 * k)); j++)dp[i][j] = inf;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < 2 * k; j++)
                dp[i][1 << j] = dis[i][e[j]];
        }
        for (int i = 1; i < (1 << (2 * k)); i++){
            if (0 == (i&(i - 1)))continue;
            for (int j = 0; j < n; j++){
                for (int sub = i; sub > 0; sub = (sub - 1)&i)
                    dp[j][i] = min(dp[j][i], dp[j][sub] + dp[j][i-sub]);
            }
            for (int j = 0; j < n; j++)vis[j] = 0;
            for (int j = 0; j < n; j++){
                int a = inf, pos = 0;
                for (int z = 0; z < n; z++)
                if (vis[z] == 0 && dp[z][i] <= a)
                    a = dp[pos = z][i];
                vis[pos] = 1;
                for (int z = 0; z < n; z++)
                    dp[pos][i] = min(dp[pos][i], dp[z][i] + dis[z][pos]);
            }
        }
        for (int j = k; j < 2 * k; j++)vis[j] = -1;
        memset(mem, -1, sizeof mem);
        mem[0] = 0;
        ans = dfs((1<<(2*k))-1);
        if (ans == inf)printf("No solution\n");
        else printf("%d\n",ans);
    }
    return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Queue;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
public class Main {
	int n, m, k, ans;
	int[][] dis = new int[N][N], dp = new int[N][1<<10];
	int[] e = new int[10];
	int[] vis = new int[N], mem = new int[1<<10];
	int check(int x){
		int a = 0, b = 0;
		for (int i = 0; i < k; i++)
		if ((x&(1 << i))>0)a++;
		for (int i = 0; i < k; i++)
		if ((x&(1 << (i + k)))>0)b++;
		if (a != b)return -1;
		int ans = inf;
		for (int i = 0; i < n; i++)
			ans = min(ans, dp[i][x]);
		return ans;
	}
	int dfs(int x){
		if (mem[x] != -1)return mem[x];
		int tmp = check(x);
		if (tmp == -1)return mem[x] = inf;
		int ans = tmp;
		for (int i = (x-1)&x; i > 0; i = (i - 1)&x){
			ans = min(ans, dfs(i) + dfs(x - i));
		}
		return mem[x] = ans;
	}
	void floyd(){
		for(int z = 0; z < n; z++)
			for(int j = 0; j < n; j++)
				for(int i = 0; i < n; i++)
					dis[i][j] = min(dis[i][j], dis[j][z] + dis[z][i]);
	}
	void input() throws Exception{
		for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)dis[i][j] = (i==j)?0:inf;
		while(m-->0){
			int u = Int() - 1, v = Int() - 1, d = Int();
			dis[u][v] = dis[v][u] = min(dis[u][v], d);
		}
	}
	void work() throws Exception{
		int T = Int(); 
		while(T-->0){
			n = Int(); m = Int(); k = Int();
			input();
			floyd();
			for (int i = 0; i < k; i++)e[i] = i; for (int i = 0; i < k; i++)e[i + k] = n - k + i;
			for (int i = 0; i < n; i++)for (int j = 0; j < (1 << (2 * k)); j++)dp[i][j] = inf;
			for (int i = 0; i < n; i++){
				for (int j = 0; j < 2 * k; j++)
					dp[i][1 << j] = dis[i][e[j]];
			}
			for (int i = 1; i < (1 << (2 * k)); i++){
				if (0 == (i&(i - 1)))continue;
				for (int j = 0; j < n; j++){
					for (int sub = i; sub > 0; sub = (sub - 1)&i)
						dp[j][i] = min(dp[j][i], dp[j][sub] + dp[j][i-sub]);
				}
				for (int j = 0; j < n; j++)vis[j] = 0;
				for (int j = 0; j < n; j++){
					int a = inf, pos = 0;
					for (int z = 0; z < n; z++)
					if (vis[z] == 0 && dp[z][i] <= a)
						a = dp[pos = z][i];
					vis[pos] = 1;
					for (int z = 0; z < n; z++)
						dp[pos][i] = min(dp[pos][i], dp[z][i] + dis[z][pos]);
				}
			}
			for(int i = 1; i < (1<<(2*k)); i++)mem[i] = -1;
			mem[0] = 0;
			ans = dfs((1<<(2*k))-1);
			if(ans == inf)out.println("No solution");
			else out.println(ans);
		}
	}

    public static void main(String[] args) throws Exception{
        Main wo = new Main();
    	in = new BufferedReader(new InputStreamReader(System.in));
    	out = new PrintWriter(System.out);
  //  	in = new BufferedReader(new InputStreamReader(new FileInputStream(new File("input.txt"))));
  //  	out = new PrintWriter(new File("output.txt"));
        wo.work();
        out.close();
    }

	static int N = 55;
	static int M = 2005;
	DecimalFormat df=new DecimalFormat("0.0000");
	static int inf = (int)1e8;
	static long inf64 = (long) 1e18*2;
	static double eps = 1e-8;
	static double Pi = Math.PI;
	static int mod = 1000000009 ;
	
	private String Next() throws Exception{
    	while (str == null || !str.hasMoreElements())
    	    str = new StringTokenizer(in.readLine());
    	return str.nextToken();
    }
    private int Int() throws Exception{
    	return Integer.parseInt(Next());
    }
    private long Long() throws Exception{
    	return Long.parseLong(Next());
    }
    private double Double() throws Exception{
    	return Double.parseDouble(Next());
    }
    StringTokenizer str;
    static Scanner cin = new Scanner(System.in);
    static BufferedReader in;
    static PrintWriter out;
  /*  
	class Edge{
		int from, to, dis, nex;
		Edge(){}
		Edge(int from, int to, int dis, int nex){
			this.from = from;
			this.to = to;
			this.dis = dis;
			this.nex = nex;
		}
	}
	Edge[] edge = new Edge[M<<1];
	int[] head = new int[N];
	int edgenum;
	void init_edge(){for(int i = 0; i < N; i++)head[i] = -1; edgenum = 0;}
	void add(int u, int v, int dis){
		edge[edgenum] = new Edge(u, v, dis, head[u]);
		head[u] = edgenum++;
	}/**/
	int upper_bound(int[] A, int l, int r, int val) {// upper_bound(A+l,A+r,val)-A;
		int pos = r;
		r--;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (A[mid] <= val) {
				l = mid + 1;
			} else {
				pos = mid;
				r = mid - 1;
			}
		}
		return pos;
	}

	int Pow(int x, int y) {
		int ans = 1;
		while (y > 0) {
			if ((y & 1) > 0)
				ans *= x;
			y >>= 1;
			x = x * x;
		}
		return ans;
	}
	double Pow(double x, int y) {
		double ans = 1;
		while (y > 0) {
			if ((y & 1) > 0)
				ans *= x;
			y >>= 1;
			x = x * x;
		}
		return ans;
	}
	int Pow_Mod(int x, int y, int mod) {
		int ans = 1;
		while (y > 0) {
			if ((y & 1) > 0)
				ans *= x;
			ans %= mod;
			y >>= 1;
			x = x * x;
			x %= mod;
		}
		return ans;
	}
	long Pow(long x, long y) {
		long ans = 1;
		while (y > 0) {
			if ((y & 1) > 0)
				ans *= x;
			y >>= 1;
			x = x * x;
		}
		return ans;
	}
	long Pow_Mod(long x, long y, long mod) {
		long ans = 1;
		while (y > 0) {
			if ((y & 1) > 0)
				ans *= x;
			ans %= mod;
			y >>= 1;
			x = x * x;
			x %= mod;
		}
		return ans;
	}

	int gcd(int x, int y){
		if(x>y){int tmp = x; x = y; y = tmp;}
		while(x>0){
			y %= x;
			int tmp = x; x = y; y = tmp;
		}
		return y;
	}
	int max(int x, int y) {
		return x > y ? x : y;
	}

	int min(int x, int y) {
		return x < y ? x : y;
	}

	double max(double x, double y) {
		return x > y ? x : y;
	}

	double min(double x, double y) {
		return x < y ? x : y;
	}

	long max(long x, long y) {
		return x > y ? x : y;
	}

	long min(long x, long y) {
		return x < y ? x : y;
	}

	int abs(int x) {
		return x > 0 ? x : -x;
	}

	double abs(double x) {
		return x > 0 ? x : -x;
	}

	long abs(long x) {
		return x > 0 ? x : -x;
	}

	boolean zero(double x) {
		return abs(x) < eps;
	}
	double sin(double x){return Math.sin(x);}
	double cos(double x){return Math.cos(x);}
	double tan(double x){return Math.tan(x);}
	double sqrt(double x){return Math.sqrt(x);}
}