首页 > 代码库 > [USACO 102]Agri-Net
[USACO 102]Agri-Net
OJ题号:POJ1258、洛谷1546
思路:Kruskal。
1 #include<cstdio> 2 #include<utility> 3 #include<vector> 4 #include<algorithm> 5 #define w first 6 #define a second.first 7 #define b second.second 8 typedef std::pair<int,std::pair<int,int> > Edge; 9 const int N=100;10 int n;11 std::vector<Edge> e;12 class UnionFindSet {13 private:14 int anc[N];15 public:16 UnionFindSet(int n) {17 for(int i=0;i<n;i++) anc[i]=i;18 }19 int Find(int x) {20 return (x==anc[x])?x:(anc[x]=Find(anc[x]));21 }22 void Union(int x,int y) {23 anc[Find(y)]=Find(x);24 }25 };26 int main() {27 scanf("%d",&n);28 for(int i=0;i<n;i++) {29 for(int j=0;j<n;j++) {30 int c;31 scanf("%d",&c);32 if(i<j) {33 e.push_back(std::make_pair(c,std::make_pair(i,j)));34 }35 }36 }37 UnionFindSet s(n);38 std::sort(e.begin(),e.end());39 int ans=0;40 for(int i=0;i<(int)e.size();i++) {41 if(s.Find(e[i].a)==s.Find(e[i].b)) continue;42 ans+=e[i].w;43 s.Union(e[i].a,e[i].b);44 }45 printf("%d\n",ans);46 return 0;47 }
[USACO 102]Agri-Net
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。