#include "bits/stdc++.h" using namespace std; class Graph{ public: int nodes; vector<list<pair<int,int>>> graph; Graph(int n,vector<pair<pair<int,int>,int>> edges) { nodes=n; graph=vector<list<pair<int,int>>>(n+1,list<pair<int,int>>()); for (pair<pair<int,int>,int> edge: edges) { pair<int,int> no_value_edge=edge.first; int value=edge.second; pair<int,int> addEdge1(no_value_edge.first,value); pair<int,int> addEdge2(no_value_edge.second,value); graph[no_value_edge.first].push_back(addEdge2); graph[no_value_edge.second].push_back(addEdge1); } } }; int primeGraph(Graph g,int start) { int size = g.nodes; int cost[size+1]; int visited[size+1]; memset(cost, INT_MAX, (size+1) * sizeof(int)); memset(visited, 0, (size+1) * sizeof(int)); cost[start]=0; visited[start]=1; for (pair<int,int> edge: g.graph[start]) { cost[edge.first]=edge.second; } int sumCost=0; for (int i = 0; i <size-1; ++i) { int minCostIndex=0; int minCost=INT_MAX; for (int j = 1; j <= size; ++j) { if (!visited[j] && cost[j]<minCost) { minCost=cost[j]; minCostIndex=j; } } visited[minCostIndex]=1; for (pair<int,int> edge: g.graph[minCostIndex]) { if (!visited[edge.first]) { cost[edge.first]= min(edge.second,cost[edge.first]); } } sumCost+=minCost; } return sumCost; } int main(){ int n; while (cin>>n) { if (!n) break; vector<pair<pair<int,int>,int>> edges(n*(n-1)/2); for (int i = 0; i < edges.size(); ++i) { int v1,v2,value; int isBuild; cin>>v1>>v2>>value>>isBuild; if (isBuild) value=0; pair<pair<int,int>,int> edge(pair<int,int>(v1,v2),value); edges[i]=edge; } Graph gra(n,edges); cout<<primeGraph(gra,1)<<endl; } return 0; }
使用Prime算法构造最小生成树,值得注意的是对于已经建立好的道路则视为cost为0