题解 | #友好城市#

解题思路

这是一个最短路径和状态压缩动态规划结合的问题。具体要求：

$n$ 个城市之间有无向边相连，边权表示距离
$2k$ 个重要城市需要两两配对，形成 $k$ 对友好城市
每对友好城市的代价是它们之间的最短路径长度
求所有可能的配对方案中，总代价最小的值

解决方案：

使用Floyd-Warshall算法计算任意两点间的最短路径
使用状态压缩DP求解最小完美匹配问题
DP状态表示已匹配的城市集合，转移时枚举新的一对城市

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

const int INF = 1e9;
const int MAXN = 100;

class Solution {
private:
    int n, k;
    int dist[MAXN][MAXN];
    vector<int> important_cities;
    
    // Floyd-Warshall算法计算最短路
    void floydWarshall() {
        for(int k = 0; k < n; ++k)
            for(int i = 0; i < n; ++i)
                for(int j = 0; j < n; ++j)
                    if(dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
    }
    
    // 状态压缩DP求最小匹配代价
    int minMatchingCost() {
        int size = important_cities.size();
        vector<int> dp(1 << size, INF);
        dp[0] = 0;
        
        for(int mask = 0; mask < (1 << size); ++mask) {
            int count = __builtin_popcount(mask);
            if(count % 2 != 0) continue;
            
            for(int i = 0; i < size; ++i) {
                if(mask & (1 << i)) continue;
                for(int j = i + 1; j < size; ++j) {
                    if(mask & (1 << j)) continue;
                    int new_mask = mask | (1 << i) | (1 << j);
                    int city1 = important_cities[i];
                    int city2 = important_cities[j];
                    dp[new_mask] = min(dp[new_mask], 
                                     dp[mask] + dist[city1][city2]);
                }
            }
        }
        return dp[(1 << size) - 1];
    }

public:
    int solve() {
        cin >> n;
        // 读入距离矩阵
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                cin >> dist[i][j];
                if(dist[i][j] == -1)
                    dist[i][j] = INF;
            }
        }
        
        // 读入重要城市
        cin >> k;
        important_cities.resize(2*k);
        for(int i = 0; i < 2*k; ++i) {
            cin >> important_cities[i];
            important_cities[i]--;  // 转为0-based索引
        }
        
        floydWarshall();
        return minMatchingCost();
    }
};

int main() {
    Solution solution;
    cout << solution.solve() << endl;
    return 0;
}

import java.util.*;

public class Main {
    static final int INF = 1000000000;
    static final int MAXN = 100;
    
    static class Solution {
        int n, k;
        int[][] dist = new int[MAXN][MAXN];
        List<Integer> importantCities = new ArrayList<>();
        
        void floydWarshall() {
            for(int k = 0; k < n; ++k)
                for(int i = 0; i < n; ++i)
                    for(int j = 0; j < n; ++j)
                        if(dist[i][k] + dist[k][j] < dist[i][j])
                            dist[i][j] = dist[i][k] + dist[k][j];
        }
        
        int minMatchingCost() {
            int size = importantCities.size();
            int[] dp = new int[1 << size];
            Arrays.fill(dp, INF);
            dp[0] = 0;
            
            for(int mask = 0; mask < (1 << size); ++mask) {
                int count = Integer.bitCount(mask);
                if(count % 2 != 0) continue;
                
                for(int i = 0; i < size; ++i) {
                    if((mask & (1 << i)) != 0) continue;
                    for(int j = i + 1; j < size; ++j) {
                        if((mask & (1 << j)) != 0) continue;
                        int newMask = mask | (1 << i) | (1 << j);
                        int city1 = importantCities.get(i);
                        int city2 = importantCities.get(j);
                        dp[newMask] = Math.min(dp[newMask], 
                                             dp[mask] + dist[city1][city2]);
                    }
                }
            }
            return dp[(1 << size) - 1];
        }
        
        int solve(Scanner sc) {
            n = sc.nextInt();
            for(int i = 0; i < n; ++i)
                for(int j = 0; j < n; ++j) {
                    dist[i][j] = sc.nextInt();
                    if(dist[i][j] == -1)
                        dist[i][j] = INF;
                }
            
            k = sc.nextInt();
            for(int i = 0; i < 2*k; ++i)
                importantCities.add(sc.nextInt() - 1);
            
            floydWarshall();
            return minMatchingCost();
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Solution solution = new Solution();
        System.out.println(solution.solve(sc));
    }
}

class Solution:
    def __init__(self):
        self.INF = 10**9
        self.n = 0
        self.k = 0
        self.dist = []
        self.important_cities = []
    
    def floyd_warshall(self):
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if self.dist[i][k] + self.dist[k][j] < self.dist[i][j]:
                        self.dist[i][j] = self.dist[i][k] + self.dist[k][j]
    
    def min_matching_cost(self):
        size = len(self.important_cities)
        dp = [self.INF] * (1 << size)
        dp[0] = 0
        
        for mask in range(1 << size):
            count = bin(mask).count('1')
            if count % 2 != 0:
                continue
            
            for i in range(size):
                if mask & (1 << i):
                    continue
                for j in range(i + 1, size):
                    if mask & (1 << j):
                        continue
                    new_mask = mask | (1 << i) | (1 << j)
                    city1 = self.important_cities[i]
                    city2 = self.important_cities[j]
                    dp[new_mask] = min(dp[new_mask], 
                                     dp[mask] + self.dist[city1][city2])
        
        return dp[(1 << size) - 1]
    
    def solve(self):
        self.n = int(input())
        self.dist = []
        for _ in range(self.n):
            row = list(map(int, input().split()))
            self.dist.append([self.INF if x == -1 else x for x in row])
        
        self.k = int(input())
        self.important_cities = list(map(lambda x: int(x)-1, input().split()))
        
        self.floyd_warshall()
        return self.min_matching_cost()

def main():
    solution = Solution()
    print(solution.solve())

if __name__ == "__main__":
    main()

算法及复杂度

算法：Floyd-Warshall + 状态压缩DP
时间复杂度： $\mathcal{O}(n^3 + k^2 \cdot 2^{2k})$ - Floyd-Warshall算法 $O(n^3)$ ，状态压缩DP部分 $O(k^2 \cdot 2^{2k})$
空间复杂度： $\mathcal{O}(n^2 + 2^{2k})$ - 距离矩阵 $O(n^2)$ ，DP数组 $O(2^{2k})$