HNUST-OJ-2187-最小生成树（邻接矩阵或邻接表）

原题复刻

思想的火花 

本题采用了邻接表的方法，不想建链表，偷懒使用了vector函数（自行百度用法）

1.

struct Node
{int v,dis;//v用来存储边的目标节点，dis为边权
}fu;

2.

vector<Node>adj[MAX];
//用vector容器存储类型为Node的结构体，adj[u]存放从顶点u出发可以到达的所有顶点

3.

int prim()
{fill(d,d+MAX,INF);//初始化所有点到原点0的距离为INF，无穷大d[0]=0;//原点到原点距离为0int ans=0;//ans用以存储从原点到所有点的最小距离for(int i=0; i<n; i++){int u=-1,minn=INF;//u表示是否存在一点未访问，且到原点距离最小的一点for(int j=0; j<n; j++)if(vi[j]==0&&d[j]<minn)u=j,minn=d[j];//按照if条件语句进行更新if(u==-1)return -1;//一点都找不到满足条件直接返回（无法生成最小生成树）vi[u]=1;//标记找到的uans+=d[u];//总距离增加；int xt;//依照题意所做的寻找本次循环找到的最短边的另外一个点是谁for(int j=0; j<adj[u].size(); j++){if(adj[u][j].dis==d[u])//寻找从u出发到达另一点距离为d[u]的点{xt=j;break;}}if(d[u])cout<<"("<<a[adj[u][xt].v]<<","<<a[u]<<"):"<<d[u]<<endl;//if防止输出自己到自己的点，按照要求输出for(int j=0; j<adj[u].size(); j++){int v=adj[u][j].v;//通过邻接表直接获得u能到达的顶点vif(vi[v]==0&&adj[u][j].dis<d[v])d[v]=adj[u][j].dis;
//如果v未访问&&以u为中介点可以使d[v]更优}}return ans;}

2.int LocateVex(string v)

for(int i = 0; i <n; ++i)if(a[i] == v)return i;//寻找v点在顶点表中的位置

代码实现 

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000
#define INF 1e+7
int n,e;
int d[MAX];
bool vi[MAX];
struct Node
{int v,dis;
}fu;
vector<Node>adj[MAX];
string a[MAX];
int prim()
{fill(d,d+MAX,INF);d[0]=0;int ans=0;for(int i=0; i<n; i++){int u=-1,minn=INF;for(int j=0; j<n; j++)if(vi[j]==0&&d[j]<minn)u=j,minn=d[j];if(u==-1)return -1;vi[u]=1;ans+=d[u];int xt;for(int j=0; j<adj[u].size(); j++){if(adj[u][j].dis==d[u]){xt=j;break;}}if(d[u])cout<<"("<<a[adj[u][xt].v]<<","<<a[u]<<"):"<<d[u]<<endl;for(int j=0; j<adj[u].size(); j++){int v=adj[u][j].v;if(vi[v]==0&&adj[u][j].dis<d[v])d[v]=adj[u][j].dis;}}return ans;}
int LocateVex(string v)
{for(int i = 0; i <n; ++i)if(a[i] == v)return i;
}
int main()
{cin>>n>>e;for(int i=0; i<n; i++)cin>>a[i];while(e--){string x1,x2;int x;cin>>x1>>x2>>x;int h1=LocateVex(x1),h2=LocateVex(x2);fu.dis=x;fu.v=h2;adj[h1].push_back(fu);fu.v=h1;adj[h2].push_back(fu);}//for(int i=0; i<n; i++)for(int j=0; j<n; j++)cin>>g[i][j];int h=prim();cout<<"minCost="<<h;}