首页 > Web开发 > 详细

[USACO 102]Agri-Net

时间:2017-06-04 20:46:06      阅读:341      评论:0      收藏:0      [点我收藏+]

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

原文:http://www.cnblogs.com/skylee03/p/6941610.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!