几个题基本都是Kruskal算法
#include<iostream> #include<vector> #include<map> #include<algorithm> using namespace std; const int maxn=200; int sum; struct home{ int x,y; int height; int state; inline bool operator < (const home &a)const{ return height<a.height; } }; vector<home> vec; int father[maxn]; int height[maxn]; void init(){ sum=0; for(int i=0;i<maxn;i++){ father[i]=i; height[i]=0; } vec.clear(); } int find(int x){ if(father[x]!=x){ father[x]=find(father[x]); } return father[x]; } void Union(int x,int y,int z,int state){ x=find(x); y=find(y); if(x!=y){ if(state==0) sum+=z; if(height[x]>height[y]) father[y]=x; else if(height[x]<height[y]) father[x]=y; else{ father[x]=y; height[y]++; } } } int main(){ int n; home h; while(cin>>n){ if(n==0)break; init(); for(int i=0;i<n*(n-1)/2;i++){ cin>>h.x>>h.y>>h.height>>h.state; if(h.state==1) Union(h.x,h.y,h.height,h.state); else vec.push_back(h); } sort(vec.begin(),vec.end()); for(int i=0;i<n*(n-1)/2;i++){ Union(vec[i].x,vec[i].y,vec[i].height,vec[i].state); } cout<<sum<<endl; } return 0; }