HDU 1879 持续畅通工程

HDU 1879 继续畅通工程

Description

Input

Output

Sample Input

Sample Output

#include<iostream>#include<cstdio>#include<vector>#include<queue>using namespace std;struct node{ int u,v,w,bo; node(int x,int y,int z,int q):u(x),v(y),w(z),bo(q){} bool operator <(const node a)const { return w>a.w; }};int rank[105],father[105];void set(int x){ rank[x]=0; father[x]=x;}int find(int x){ if(x!=father[x]) father[x]=find(father[x]); return father[x];}bool merge(int u,int v){ int x=find(u); int y=find(v); if(x!=y) { if(rank[x]>rank[y]) { father[y]=x; } else { if(rank[x]==rank[y]) { rank[y]++; } father[x]=y; } return true; } return false;}int main(){ //freopen("in.txt","r",stdin); int n; int u,v,w,bo,ans; while(scanf("%d",&n)) { if(n==0)break; ans=0; priority_queue<node>prique; n=n*(n-1)>>1; while(n--) { scanf("%d%d%d%d",&u,&v,&w,&bo); if(bo)w=0; prique.push(node(u,v,w,bo)); set(u),set(v); } while(!prique.empty()) { if(merge(prique.top().u,prique.top().v)) ans+=prique.top().w; prique.pop(); } printf("%d\n",ans); } return 0;}