题意分析

题目描述了一个匹配问题：给定一组幻灯片（slides）和一组点（points），每个幻灯片是一个矩形区域，每个点位于某个幻灯片的区域内。需要确定每个点与幻灯片的对应关系，并找出那些唯一的匹配对（即如果去掉该匹配对，最大匹配数会减少）。

解题思路

1. 输入处理：读取每个幻灯片的矩形坐标和每个点的坐标，构建二分图，其中一边是幻灯片，另一边是点。如果点位于幻灯片的矩形区域内，则在二分图中添加对应的边。
2. 匈牙利算法：使用匈牙利算法计算初始的最大匹配数。
3. 关键匹配检测：对于每一个匹配对，暂时移除该对，重新计算最大匹配数。如果最大匹配数减少，则该匹配对是关键的（即唯一的）。
4. 输出结果：输出所有关键的匹配对，如果没有则输出“none”。

代码分析

1. 数据结构：

   • slides结构体存储幻灯片的矩形坐标。
   • g数组是邻接表，表示幻灯片到点的边。
   • vis、link、save数组用于匈牙利算法的实现。

2. 匈牙利算法：

   • dfs函数实现增广路径的查找。
   • hungary函数计算最大匹配数。

3. 关键匹配检测：

   • 在print函数中，遍历每个匹配对，暂时移除后重新计算最大匹配数，判断是否为关键匹配。

代码

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

const int INF = INT_MAX;

void solve(int n, int k, const vector<int>& positions) {
    // dp[i][j]：前i个餐厅建j个仓库的最小总距离
    vector<vector<int> > dp(n+1, vector<int>(k+1, INF));
    // cost[l][r]：餐厅l到r由一个仓库服务的最小总距离
    vector<vector<int> > cost(n+1, vector<int>(n+1, 0));
    
    // 预处理cost数组
    for (int l = 1; l <= n; ++l) {
        for (int r = l; r <= n; ++r) {
            int median = positions[(l + r) / 2 - 1];  // 中位数位置最优
            for (int i = l; i <= r; ++i) {
                cost[l][r] += abs(positions[i-1] - median);
            }
        }
    }

    // 初始化dp
    for (int i = 1; i <= n; ++i) {
        dp[i][1] = cost[1][i];
    }

    // 动态规划
    for (int j = 2; j <= k; ++j) {
        for (int i = 1; i <= n; ++i) {
            for (int m = 1; m < i; ++m) {
                if (dp[m][j-1] + cost[m+1][i] < dp[i][j]) {
                    dp[i][j] = dp[m][j-1] + cost[m+1][i];
                }
            }
        }
    }

    // 回溯找出仓库位置
    vector<pair<int, pair<int, int> > > depots;
    int last = n;
    for (int j = k; j >= 1; --j) {
        if (j == 1) {
            int median_pos = (1 + last) / 2;
            pair<int, pair<int, int> > depot;
            depot.first = median_pos;
            depot.second.first = 1;
            depot.second.second = last;
            depots.push_back(depot);
            break;
        }
        for (int m = 1; m < last; ++m) {
            if (dp[last][j] == dp[m][j-1] + cost[m+1][last]) {
                int median_pos = (m+1 + last) / 2;
                pair<int, pair<int, int> > depot;
                depot.first = median_pos;
                depot.second.first = m+1;
                depot.second.second = last;
                depots.push_back(depot);
                last = m;
                break;
            }
        }
    }
    reverse(depots.begin(), depots.end());

    // 输出结果
    static int case_num = 0;
    cout << "Chain " << ++case_num << endl;
    for (size_t i = 0; i < depots.size(); ++i) {
        cout << "Depot " << i+1 << " at restaurant " << depots[i].first 
             << " serves restaurants " << depots[i].second.first 
             << " to " << depots[i].second.second << endl;
    }
    cout << "Total distance sum = " << dp[n][k] << endl;
    cout << endl;
}

int main() {
    int n, k;
    while (cin >> n >> k && (n != 0 || k != 0)) {
        vector<int> positions(n);
        for (int i = 0; i < n; ++i) {
            cin >> positions[i];
        }
        solve(n, k, positions);
    }
    return 0;
}