题解 | #素数伴侣# 拓扑排序

题意整理

略

解题思路

首先，考虑一种简单的情况，枚举每对数字，一旦这对数字的和是素数，我们就将结果结果加1，并将这对数字标记为已访问，这样就会产生一种如题目中描述的情况。例如，数组为[5, 6, 2, 13]，我们会先枚举到[5, 6]这对并将它们标记为已访问，这样[5, 2]和[6, 13]这种更优的情况我们就考虑不到了。

如果我们能事先知道每个数与其他数的配对情况，我们就能从整体上考虑应该怎么分配伴侣。由此我们可以想到用一个无向图来表示每个数与其他数的配对情况，如下图所示，图中每个点表示一个数字，每条边表示边所连接的两点对应数字之和为素数。

在实现时由于答案只要求伴侣的数量，并没要求输出具体的每对伴侣，所以无向图建立好之后我们就可以不用再考虑点对应的数字而只需要考虑每个数字对应图中的索引，即如下图，数字的索引由我们读入该数字的顺序决定：

此时求最佳伴侣方案的问题已经可以看成一个拓扑排序的问题了，具体算法如下：

1. 我们每次都选取一个度数最小且不为0的点（因为度数为0说明没有边相连，没有考虑必要）如有多个则选任意一个，并选取该点相邻的任意一个还没访问的点作为伴侣；
2. 分别将这对点的相邻点的度数减1，访问标记置1，答案加1；
3. 重复1-2最多 N/2 次，N为输入的数字个数。

这里简单说明下正确性，由于我们每次会选2个点X和Y，X为我们选取的度数最小点，Y为X任意一未访问过的相邻点。经过上述步骤2的处理后，其他没被选取到的点的度数可能会减0、1或2。

情况1：如果某点Z度数没变，则说明它与我们选取的两点没有直连边，则对该点没有影响；

情况2：如果某点Z度数减去了1，此时如果该点度数变为了0，说明该点原本度数为1，由于X为最小度数点，说明X度数也为1，说明X和Z通过Y相连，两者选谁和Y搭配是等价的，否则Z度数不为0其还有其他选择可选；

情况3：如果Z度数减去了2，说明Z与X和Y相连，剩余考虑与情况2相同

时间复杂度

• 建图时间为N * N * sqrt(val) =O(N²sqrt(val))
• 拓扑排序时间为N / 2 * N = O(N²)
• 总体时间复杂度为O(N²sqrt(val))

#include <bits/stdc++.h>
using namespace std;
// 是否为素数
bool is_prime(const int& x){
    if(x == 2) return true;
    for(int i = 2; i <= sqrt(x); ++i){
        if(x % i == 0) return false;
    }
    return true;
}
int main() {
    int n;
    cin >> n;
    vector<vector<int>> matrix(n);
    vector<int> nums(n);
  	// 对每对伴侣数之和进行处理，如果为素数则代表两者之间有一条边
    for(int i = 0; i < n; ++i){
        cin >> nums[i];
        for(int j = i - 1; j >= 0; --j){
            if(is_prime(nums[i] + nums[j])){
                matrix[i].emplace_back(j);
                matrix[j].emplace_back(i);
            }
        }
    }
  	// 这里再利用了上面的nums数组，从记录每个数字改为记录每个数字对应索引包含的边数
  	// 因为图建完后数字本身已经没用了，我们已经知道了哪几对之间会构成素数
    for(int i = 0; i < n; ++i){
        nums[i] = matrix[i].size();
        // cout << nums[i] << endl;
    }
  	// 额外加入一个点作为是否为合法索引的判断条件
    nums.emplace_back(101);
    int res = 0;
    vector<bool> visited(n, false);
    for(int i = 0; i < n / 2; ++i){
        int index = n;
	  	// 每次选取未被选择过且当前边数不为0且边数最小的点
        for(int j = 0; j < n; ++j){
            if(visited[j] || nums[j] == 0) continue;
            if(nums[index] > nums[j]) index = j;
        }
	 	// 如果已经没有合法的点了直接退出循环
        if(index == n) break;
        visited[index] = true;
        int pair;
	  	// 从被选取点的相邻点中找出另一个没被访问过的点
        for(int j : matrix[index]){
            nums[j] --;
            if(!visited[j]){
                pair = j;
            }
        }
        visited[pair] = true;
        res++;
	  	// 将另一个被选取点的相邻点的边数减一
        for(int j:matrix[pair]) nums[j] --;
    }
    cout << res << endl;
    return 0;
}