題目鏈接：點擊打開鏈接
題意:
第一行輸入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#include #include #include #include
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);}
}
