P1550 [USACO08OCT] Watering Hole G

使用并查集将水井的打井钱看作是边加入edges中即可#includebits/stdc.h using namespace std; struct Edge{ int u,v,w; }; vectorint parent; int find(int x){ if(x!parent[x]){ parent[x]find(parent[x]); } return parent[x]; } bool unite(int x,int y){ int findxfind(x); int findyfind(y); if(findxfindy){ return false; } else{ parent[findx]findy; return true; } } bool cmp(const Edge a,const Edge b){ return a.wb.w; } int main(){ int n; cinn; vectorEdge edges; for(int i1;in;i){ int price; cinprice; edges.push_back({0,i,price}); } vectorvectorint k(n1,vectorint(n1)); for(int i1;in;i){ for(int j1;jn;j){ cink[i][j]; } } for(int i1;in;i){ for(int ji1;jn;j){ edges.push_back({i,j,k[i][j]}); } } sort(edges.begin(),edges.end(),cmp); parent.resize(n1); for(int i0;in;i){ parent[i]i; } int res0; int ant0; for(const auto e:edges){ if(unite(e.u,e.v)){ rese.w; ant; if(antn){ break; } } } coutresendl; return 0; }