#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
bool vis[1000];
template <class TypeOfVer, class TypeOfEdge>
class adjmatrix_graph {
private:
int Vers; //顶点数
int Edges; //边数
TypeOfEdge **edge; //存放邻接矩阵（TypeOfEdge表示顶点关系类型。对于无权图，用1或0，表示相邻否；对于带权图，则为权值类型）
TypeOfVer *ver; //存放结点值
TypeOfEdge noEdge; //邻接矩阵中的∞的表示值
string GraphKind; //图的种类标志
bool DFS(int u, int &num, int visited[]); // DFS遍历（递归部分）
bool CheckRoute(int u, int v, int visited[]);
public:
adjmatrix_graph(const string &kd, int vSize, const TypeOfVer d[], const TypeOfEdge noEdgeFlag); //构造函数构造一个只有结点没有边的图。4个参数的含义：图的类型、结点数、结点值和邻接矩阵中表示结点间没有边的标记（无权图：0，有权图：输入参数定）
adjmatrix_graph(const string &kd, int vSize, int eSize, const TypeOfVer d[], int **e); //构造函数构造一个无权图。5个参数的含义：图的类型、结点数、边数、结点集和边集
adjmatrix_graph(const string &kd, int vSize, int eSize, const TypeOfEdge noEdgeFlag, const TypeOfVer d[], int e[][2], const TypeOfEdge w[]); //构造函数构造一个有权图。7个参数的含义：图的类型、结点数、边数、无边标记、结点集、边集、权集
bool GraphisEmpty() {
return Vers == 0;
} //判断图空否
string GetGraphKind() {
return GraphKind;
}
bool GetVer(int u, TypeOfVer &data); //取得G中指定顶点的值
int GetFirstAdjVex(int u, int &v); //返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1
int GetNextAdjVex(int u, int v, int &w); //返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1
bool PutVer(int u, TypeOfVer data); //对G中指定顶点赋值
bool InsertVer(const TypeOfVer &data); //往G中添加一个顶点
bool Printvers(); //输出顶点集
int LocateVer(TypeOfVer data); //返回G中指定顶点的位置
bool PrintMatrix(); //输出邻接矩阵
bool CheckRoute(int u, int v);
int Get_InDegree(int u);
int Get_Degree(int u);
bool ExistEdge(int u, int v);
bool TopSort();
bool U_Judge_Cir();
int GetVerNum() {
return Vers;
} //取得当前顶点数
int GetEdgeNum() {
return Edges;
} //取得当前边数
bool Insert_Edge(int u, int v); //无权图插入一条边
bool Insert_Edge(int u, int v, TypeOfEdge w); //有权图插入一条边
bool DeleteVer(const TypeOfVer &data); //往G中删除一个顶点
bool Delete_Edge(int u, int v); //无权图删除一条边
bool Delete_Edge(int u, int v, TypeOfEdge w); //有权图删除一条边
void DFS_Traverse(int u); // DFS遍历（外壳部分）
void BFS_Traverse(int u); // BFS遍历
bool Prim(int u, int adjvex[], TypeOfEdge lowcost[]); // Prim算法求最小生成树
~adjmatrix_graph(){}; //析构函数
};
template <class TypeOfVer, class TypeOfEdge>
adjmatrix_graph<TypeOfVer, TypeOfEdge>::adjmatrix_graph(const string &kd, int vSize, int eSize, const TypeOfEdge noEdgeFlag, const TypeOfVer d[], int e[][2], const TypeOfEdge w[]) {
//构造函数构造一个有权图。7个参数的含义：图的类型、结点数、边数、无边标记、结点集、边集、权集
GraphKind = kd;
Vers = vSize;
Edges = eSize;
noEdge = noEdgeFlag;
ver = new TypeOfVer[vSize];
edge = new TypeOfEdge *[eSize];
for (int i = 0; i < vSize; i++) ver[i] = d[i];
for (int i = 0; i < vSize; i++) {
edge[i] = new TypeOfEdge[vSize];
for (int j = 0; j < vSize; j++) {
edge[i][j] = noEdge;
}
}
for (int i = 0; i < eSize; i++) {
edge[e[i][0]][e[i][1]] = w[i];
if (GraphKind == "UDN")
edge[e[i][1]][e[i][0]] = w[i];
}
}
template <class TypeOfVer, class TypeOfEdge>
bool adjmatrix_graph<TypeOfVer, TypeOfEdge>::Printvers() {
for (int i = 0; i < Vers; i++) {
if (i) cout << ' ';
cout << ver[i];
}
cout << endl;
return 0;
}
template <class TypeOfVer, class TypeOfEdge>
bool adjmatrix_graph<TypeOfVer, TypeOfEdge>::PrintMatrix() {
for (int i = 0; i < Vers; i++) {
for (int j = 0; j < Vers; j++) {
cout << edge[i][j] << '\t';
}
cout << endl;
}
return true;
}
template <class TypeOfVer, class TypeOfEdge>
bool adjmatrix_graph<TypeOfVer, TypeOfEdge>::Prim(int u, int adjvex[], TypeOfEdge lowcost[]) {
bool flag[Vers] = {false};
int dist[Vers];
for (int i = 0; i < Vers; i++) dist[i] = noEdge;
dist[u] = 0;
for (int i = 0; i < Vers; i++) {
int minidx = -1;
for (int j = 0; j < Vers; j++) {
if (!flag[j] && (minidx == -1 || dist[minidx] > dist[j])) {
minidx = j;
}
}
lowcost[minidx] = dist[minidx];
flag[minidx] = true;
for (int j = 0; j < Vers; j++) {
if (dist[j] > edge[minidx][j]) {
dist[j] = edge[minidx][j];
adjvex[j] = minidx;
}
}
}
return 1;
}
int main() {
string kind;
int vSize, eSize, start, noEdgeFlag;
cin >> kind; //输入类型
cin >> vSize; //结点数
char d[vSize];
for (int i = 0; i < vSize; i++) {
cin >> d[i]; //结点集
}
cin >> noEdgeFlag; // 无边标记
cin >> eSize; //边数
int edgs[eSize][2], w[eSize];
for (int i = 0; i < eSize; i++) { //输入边集
cin >> edgs[i][0] >> edgs[i][1];
}
for (int i = 0; i < eSize; i++) { //输入边集
cin >> w[i];
}
cin >> start;
adjmatrix_graph<char, int> T(kind, vSize, eSize, noEdgeFlag, d, edgs, w); //构造图
cout << T.GetGraphKind() << endl;
T.Printvers(); //打印顶点集
cout << endl;
T.PrintMatrix(); //打印邻接表
int adjvex[vSize], lowcost[vSize];
T.Prim(start, adjvex, lowcost);
for (int i = 0; i < vSize - 1; i++) {
if (i != start) {
// （邻接点, 自己, 权值）
cout << '(' << d[adjvex[i]] << ',' << d[i] << ',' << lowcost[i] << ')' << ',';
}
}
if (vSize - 1 != start)
cout << '(' << d[adjvex[vSize - 1]] << ',' << d[vSize - 1] << ',' << lowcost[vSize - 1] << ')';
return 0;
}
