c 网站开发人员工具,seo外包团队,常州模板网站建设信息,微信网站链接网站建设F : 道路建设 (Ver. I)
Description
有N个村庄#xff0c;编号从1到N#xff0c;你应该建造一些道路#xff0c;使每个村庄都可以相互连接。 两个村A和B是相连的#xff0c;当且仅当A和B之间有一条道路#xff0c;或者存在一个村C使得在A和C之间有一条道路#xff0c;并…F : 道路建设 (Ver. I)
Description
有N个村庄编号从1到N你应该建造一些道路使每个村庄都可以相互连接。 两个村A和B是相连的当且仅当A和B之间有一条道路或者存在一个村C使得在A和C之间有一条道路并且C和B相连。 现在一些村庄之间已经有一些道路你的任务就是修建一些道路使所有村庄都连通起来并且所有道路的长度总和是最小的。
Input
测试数据有多组 第一行是整数N3 N 100代表村庄的数量。 然后是N行其中第i行包含N个整数这些N个整数中的第j个是村庄i和村庄j之间的距离距离是[1,1000]内的整数。 然后是整数Q0 Q N *N 1/ 2接下来是Q行每行包含两个整数a和b1 a b N代表着村庄a和村庄b之间的道路已经建成。
Output
对于每组测试数据 输出一个整数表示要构建的道路的长度总和最小值
Sample
Input
3
0 990 692
990 0 179
692 179 0
1
1 2Output
179解题思路
最小生成树啊连接所有点并且让他们的权值之和最小这里面需要注意的就是已经修好路的两村庄的处理而且这还是无向图也就是要处理两次并且距离设为很小的数比较好。思路就是这些了剩下的就找个prim算法或者kruscal操一下输出最小值。
AC代码
#include iostream
#include vector
#include limits
using namespace std;const double MAX_WEIGHT numeric_limitsdouble::max();
const double ALREADY_CONNECTED 1e-7;int PrimMinimumSpanningTree(const vectorvectordouble graph) {int n graph.size();vectordouble key(n, MAX_WEIGHT);vectorbool includedInMST(n, false);key[0] 0;int totalWeight 0;for (int count 0; count n; count) {double minKey MAX_WEIGHT;int minKeyNode -1;for (int v 0; v n; v) {if (!includedInMST[v] key[v] minKey) {minKey key[v];minKeyNode v;}}includedInMST[minKeyNode] true;totalWeight key[minKeyNode];for (int v 0; v n; v) {if (graph[minKeyNode][v] !includedInMST[v] graph[minKeyNode][v] key[v]) {key[v] graph[minKeyNode][v];}}}return totalWeight;
}int main() {int n;while (cin n) {vectorvectordouble graph(n, vectordouble(n));for (int i 0; i n; i)for (int j 0; j n; j)cin graph[i][j];int m;cin m;for (int i 0; i m; i) {int a, b;cin a b;graph[a - 1][b - 1] graph[b - 1][a - 1] ALREADY_CONNECTED;}cout PrimMinimumSpanningTree(graph) endl;}return 0;
}
