畅通工程之局部最小花费问题 (C++)

题目：

思路：

代码：

结果

题目：

思路：

详细思路都在代码注释里。

代码：

#include<iostream>//无向图邻接矩阵
#include<map>
#include<algorithm>
#define mvnum 1005
using namespace std;
typedef int Vertextype;//顶点数据类型
map<Vertextype, int> mp;
typedef struct
{int data;int build;
}Arctype;//边权值类型
typedef struct
{Vertextype vexs[mvnum];//顶点表Arctype arcs[mvnum][mvnum];//邻接矩阵int vexnum, arcnum;//当前图的点数和边数
}AMGraph;
typedef struct
{Vertextype head;//始点Vertextype tail;//终点int w;//权值int build;
}edge;//边
int v[mvnum];//辅助数组，记录连通分支
edge e[50000];
bool Creategraph(AMGraph& G)
{cin >> G.vexnum;//输入总顶点数G.arcnum = G.vexnum * (G.vexnum - 1) / 2;//总边数for (int i = 1; i <= G.vexnum; i++)//初始化邻接矩阵for (int j = 1; j <= G.vexnum; j++)G.arcs[i][j].data = 0;for (int k = 0; k < G.arcnum; k++)//构造邻接矩阵{Vertextype v1, v2;int w, d;int t = 0;cin >> v1 >> v2 >> w >> d;//输入一条边的顶点及边的权值int i = v1;int j = v2;//确定v1和v2在G中的位置if (d == 1)//已经建造G.arcs[i][j].data = 0;//即不用再花钱elseG.arcs[i][j].data = w;//边<v1,v2>的权值置为wG.arcs[i][j].build = d;//是否建造G.arcs[j][i] = G.arcs[i][j];//无向图是对称图e[k].head = i, e[k].tail = j, e[k].w = G.arcs[i][j].data, e[k].build = d;}return 1;
}
/*void Print(AMGraph G)
{cout << "邻接矩阵：" << endl;for (int i = 1; i <= G.vexnum; i++){for (int j = 1; j <= G.vexnum; j++)cout << G.arcs[i][j].data << " ";cout << endl;}
}*/
bool cmp(edge a, edge b)
{if (a.w == b.w)return a.build > b.build;return a.w < b.w;
}
int Klsk(AMGraph& G)
{int sum = 0;//cout << "边:" << endl;sort(e, e + G.arcnum, cmp);for (int i = 1; i <= G.vexnum; i++)v[i] = i;//自成连通分量for (int i = 0; i < G.arcnum; i++){int v1 = e[i].head;//取其位置int v2 = e[i].tail;//取其位置int vs1 = v[v1];//取其连通分量int vs2 = v[v2];//取其连通分量if (vs1 != vs2)//不为同一连通分量且建造通路{sum += e[i].w;//cout << e[i].head << " " << e[i].tail << " " << e[i].w << endl;for (int j = 1; j <= G.vexnum; j++)if (v[j] == vs2)//更新连通分量v[j] = vs1;}}return sum;
}
int main()
{AMGraph G;Creategraph(G);//Print(G);int ans = Klsk(G);cout << ans << endl;
}