注意：2018年复试题目由于一些~~不可告人的原因~~，无法公布。目前只可以放出来第三题。

此复试题目是根据博客园博主林木子发布的博客发布的博客整理复原。为了恢复试题的原貌，我根据试题要求进行合理的脑补，按照oj系统的风格补全了试题的Problem Description、Input、Output、Sample Input、Sample Out等内容，并加入了详解、具体的代码实现。因为是复原版，不能保证当时的题目就是这么呈现的，也不能说明考场上的试题就是oj风格叙述的，仅供大家参考。有什么错误、不合理的地方欢迎指出。
原创不易，还请大家多支持

第三题

Problem Description

瓜农王大爷去年种西瓜赚了不少钱。看到收入不错，今年他又重新开辟了n个西瓜地。为了能给他的n个西瓜地顺利的浇上水，对于每个西瓜地他可以选择在本地打井，也可以修管道从另一个瓜地（这个瓜地可能打了井；也可能没打井，他的水也是从其他瓜地引来的）将水引过来。当然打井和修管道的费用有差别。已知在第i个西瓜地打井需要耗费wi元，在第i、j个西瓜地之间修管道需要耗费p(i,j)元。现在的问题是：王大爷要想使所有瓜地都被浇上水，至少需要花费多少钱（打井与修管道的费用和）？

Input

第1行，一个正整数n，代表西瓜地的数量。接下来n行，依次给出整数w1..wn（每块西瓜地的打井费用）。紧接着是一个n*n的整数矩阵，矩阵的第i行第j列的数代表p(i,j)两块西瓜地之间建立管道的费用。每行的两个数之间有一个空格隔开。1<=N<=300;1<=wi<=100000;p(i,i)=0;1<=p(i,j)=p(j,i)<=100000。

Output

编写程序确定在哪些（个）瓜地打井，哪些西瓜地之间修管道，以输出最小费用。

Sample Input

6
5
4
4
3
1
20
0 2 2 2 9 9
2 0 3 3 9 9
2 3 0 4 9 9
2 3 4 0 9 9
9 9 9 9 0 9
9 9 9 9 9 0

Sample Output

刚拿到这道题的时候我感觉是在考察最短路径问题，但若看做是最短路径就会有无法处理打井这一情况的问题。所以，我们可以把此问题抽象为求最小生成树，但不是传统意义上的最小生成树。首先我们需要对条件进行处理，把这n块地看成一张图中的n个点，把在某处打井也看做一个点，这样图中就有了2n个点。以样例输入为例，如图：数字表示n个地块，数字附近的蓝色点表示可在该地块打井，加起来共有12个点。然后我们考虑这个特殊图的最小生成树的求法。

使用Kruskal 算法的思路求解最小生成树，Kruskal 求解一般图的最小生成树的方法是始终选择权值最小的一条边，并把联通的点纳入集合，当集合中纳入所有的点时就求得了最小生成树。这里我们只需修改Kruskal 算法中把点纳入集合的策略就可达到我们的目的。首先，将所有地块打井的费用看做是图中的一条边，现在，图中共有6+6*5/2=21条边。其中还有一些边暂时不符合我们的要求，因为两地之间若要有边联通必然有一地有水源，所以两地均没有水源的边我们暂时先不考虑。

为了达到这一目的，我们可以使用一个变量保存目前可选的边，并从中选择一个权值（花费）最小的边，并把已有水源的点从保存没有水源的集合中去除，当集合中没有元素的时候，就得到了最小生成树，即得到了最小花费。下图是整个流程。

此代码已在洛谷P1550 USACO08OCT打井Watering Hole AC

#include <stdio.h>
#include <queue>
#include <map>
using namespace std;
struct Way//取水方式结构
{
    int a, b;//a表示修管道的水源地，b表示目的地；若供水方式为打井，则a为-1
    int cost;//花费
    //int type;//0表示打井，1表示修管道
    bool operator > (const Way& A) const {
        return cost > A.cost;
    }
};
int edges[301][301];//保存输入的修管道花费
map<int, int> m;//使用哈希表记录还没有水源的地块
priority_queue<Way, vector<Way>, greater<Way> > temp;//保存备选的取水方式
int main() {
    int n;
    int ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)//初始时将所有地块设置为没有水源
        m[i] = 0;
    for (int i = 1; i <= n; i++)//输入打井的费用
    {
        Way w;
        scanf("%d", &w.cost);
        w.a = -1;
        w.b = i;
        //.w.type = 0;
        temp.push(w);//开始先把所有打井方式记为备选
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &edges[i][j]);//输入修管道的费用
    while (!m.empty())//若还有地块没有水源则继续
    {
        Way c = temp.top();
        if (m.find(c.b) != m.end())//若该地块没有水源
        {
            temp.pop();//弹出该供水方式
            m.erase(c.b);//标记为已有水源
            ans += c.cost;//累加费用
            for (int i = 1; i <= n; i++)//将所有可向当前打井地块修管道的地块加入备选队列
            {
                if (i != c.b) {//若不是修向自身的管道,则加入备选
                    Way t;
                    t.a = c.b;
                    t.b = i;
                    t.cost = edges[c.b][i];
                    //t.type = 1;
                    temp.push(t);
                }
            }
        }
        else
            temp.pop();//弹出不满足条件的边
    }
    printf("%d\n", ans);
    return 0;
}

为了方便快捷高效率的求得所有可选边中权值最小的，我们需要使用堆数据结构。它可以以 O(logn)的复杂度取得最小元素。为了绕过对堆的实现，我们使用标准模板库中的相应的标准模板——优先队列。利用语句priority_queue<Way> temp;建立一个保存元素为Way的堆temp，但是请特别注意这样建立的堆其默认为大
顶堆，即我们从堆顶取得的元素为整个堆中最大的元素。而我们恰恰需要取得堆中最小的元素，于是我们使用如下语句定义一个小顶堆：priority_queue<Way, vector<Way>, greater<Way>> temp; 其次，为了方便确定某地块有没有通水源，使用了运用hash的map数据类型，我们可以直接通过地块号来确定是否有水源