题目描述
你与牛牛、牛妹一起出国旅行，在目的地周围一共有n家酒店，这n家酒店之间通过道路联通，这n家酒店之间通过n-1跳道路连通，没两家酒店之间存在一条唯一路径。
由于你们每个人都有自己偏好的酒店，你们决定各自选择酒店入住，第二天一早再到某个酒店集合（集合的酒店可以不是三个人入住的酒店）。由于你很聪明，你选择的集合点必定使得三个人抵达该酒店的距离之和最小。
已知每个人的偏好酒店清单，并且每个人偏好清单中的酒店被选择的概率相同，那么第二天一早，三个人各自从入住酒店到达集合的酒店的最短路程之和的期望是多少？
输入描述:
Each input file contains one test case. Each case starts with a line containing 2 numbers N (≤500), and M, which are the total number of cities, and the number of highways, respectively. Then M lines follow, each describes a highway by 4 integers: City1 City2 Cost Status where City1 and City2 are the numbers of the cities the highway connects (the cities are numbered from 1 to N), Cost is the effort taken to repair that highway if necessary, and Status is either 0, meaning that highway is destroyed, or 1, meaning that highway is in use.
Note: It is guaranteed that the whole country was connected before the war.
输出描述:
For each test case, just print in a line the city we must protest the most, that is, it will take us the maximum effort to rebuild the connection if that city is conquered by the enemy.
In case there is more than one city to be printed, output them in increasing order of the city numbers, separated by one space, but no extra space at the end of the line. In case there is no need to repair any highway at all, simply output 0.
输入例子1:
4 51 2 1 11 3 1 12 3 1 02 4 1 13 4 1 0
输出例子1:
1 2
输入例子2:
4 5
1 2 1 1
1 3 1 1
2 3 1 0
2 4 1 1
3 4 2 1
输出例子2:
0
当时的想法
其实写的时候是想到了正确算法的，遍历所有的城市，在每个城市被占领时算一次最小生成树。但是一开始以为这么搞会超时，结果竟然不会超= =然后当时2个点没过，是因为忽略了条件有BUG，修复被摧毁的铁路时没有去除掉连接了被占领了的城市。
算法分析
简单介绍一下最小生成树：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。可通过普利姆算法、克鲁斯卡尔算法求解。这道题要求求出城市被占领后，连通整个国家所有其它城市的开销，显然是一个最小生成树问题，只不过有一些edge的权值为0（因为有些铁路本来就是好的，使用它们没有开销）。
最小生成树算法介绍：https://blog.csdn.net/qq_36951116/article/details/83089039
对于Prim算法和Kruskal算法可以参考上面的博客，这里就不展开讲了。简单来说就是，Prim算法从起始点开始，从所有邻接节点中找权值最小的edge加入；Kruskal算法从整个图中找权值最小的edge，如果该边连接了两个互不连通的区域那就将该edge加入。
对于该题，记节点数量为V，边的数量为E，不采用堆优化的Prim算法的复杂度为
，采用堆优化的Prim算法复杂度为
，采用并查集优化的Kruskal算法的复杂度为
。显然，稠密图用Prim算法更快，稀疏图用Kruskal算法更快。
用Prim算法不用堆优化是会TLE的，但是用堆优化涉及到一个问题——算法进行中涉及到对已有邻接节点权值的更新，譬如本来从A-C的开销为7，然后根据贪心算法扩展了B至图中，B-C的开销仅为4，那么我们就需要更新邻接表（邻接表由一个小顶堆构成，通常为优先队列）中城市C的权值。在堆中找到C的位置并更新的复杂度高达
，通常的做法是不管原先开销为7的C节点，再扔一个开销为4的C节点进去。该方法同样适用于堆优化的Djkstra算法。
Kruskal算法需要用并查集查询子区域，在该题中将子区域的数量存下来是一个不错的选择，可以提前剪枝。并查集的代码要说简单也是真的简单，就这么一点，弄明白背下来也是非常简单的。
int getRoot(int c)
{
if (root[c] == c)
return c;
root[c] = getRoot(root[c]);
return root[c];
}
AC代码（Kruskal）
注意，该算法中大部分开销都在排序中，如果将destroy的和available的铁路分开，只对destopy的进行排序可以提速。
#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#define INF 0x7fffffff
using namespace std;
typedef struct _edge
{
int c1;
int c2;
int cost;
int available;
bool operator<(const struct _edge e)
{
if (available != e.available)
return available > e.available;
return cost < e.cost;
}
} edge;
int N, M;
int root[505];
vector<edge> edges;
int getRoot(int c)
{
if (root[c] == c)
return c;
root[c] = getRoot(root[c]);
return root[c];
}
int Kruskal(const int conquered)
{
int cost = 0, region = N - 1;
for (int _ = 1; _ <= N; ++_)
root[_] = _;
for (auto &it : edges)
{
if (it.c1 == conquered || it.c2 == conquered || getRoot(it.c1) == getRoot(it.c2))
continue;
cost += it.cost;
root[getRoot(it.c1)] = getRoot(it.c2);
if (--region == 1)
break;
}
return region == 1 ? cost : INF;
}
int main()
{
int maxCost = 0;
vector<int> res;
cin >> N >> M;
for (int i = 0; i < M; ++i)
{
edge e;
scanf("%d%d%d%d", &e.c1, &e.c2, &e.cost, &e.available);
if (e.available)
e.cost = 0;
edges.emplace_back(e);
}
sort(edges.begin(), edges.end());
for (int i = 1; i <= N; ++i)
{
int cost = Kruskal(i);
if (cost > maxCost)
{
maxCost = cost;
res.clear();
res.push_back(i);
}
else if (cost == maxCost)
res.push_back(i);
}
if (!maxCost)
cout << 0 << endl;
else
{
cout << res[0];
for (int i = 1; i < res.size(); ++i)
cout << " " << res[i];
cout << endl;
}
system("pause");
}
若有收获，就点个赞吧
0 人点赞
