poj

http://poj.org/problem?id=2377

bessie要为FJ的N个农场联网，给出M条联通的线路，每条线路需要花费C,因为意识到FJ不想付钱，所以bsssie想把工作做的很糟糕，她想要花费越多越好，并且任意两个农场都需要连通，并且不能存在环。后面两个条件保证最后的连通图是一棵树。

输出最小花费，如果没办法连通所有节点输出-1.

最大生成树问题，按边的权值从大道小排序即可，kruskal算法可以处理重边的情况，但是在处理的时候，不能仅仅因为两个节点在同一个连通子图就判断图不合法，只是不需要处理这条边，也就是不要加入并查集即可，重边也是一样。

所以只要判断图是否连通即可，但是也不能因为单单判断每个节点是否被访问过，因为就算全部被访问，还是可能不会连通。

只要判断加入并查集的边的条数是否等于n-1即可。上面都是自己开始做的没想清楚或者导致wa的，所以写下来作为自己的一点想法。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct edge
 7 {
 8     int u,v,cost;
 9     edge() {}
10     edge(int x,int y,int z)
11     {
12         u=x;
13         v=y;
14         cost=z;
15     }
16     bool operator <(const edge& a) const
17     {
18         return cost>a.cost;
19     }
20 };
21 
22 edge es[20010];
23 int par[1010];
24 int n,m;
25 void init()
26 {
27     for(int i=1;i<=n;i++) par[i]=i;
28 }
29 
30 int find(int x)
31 {
32     return x==par[x]?x:par[x]=find(par[x]);
33 }
34 
35 void unite(int x,int y)
36 {
37     x=find(x);
38     y=find(y);
39     if(x!=y) par[x]=y;
40 }
41 
42 long long kruskal()
43 {
44     sort(es,es+m);
45     //for(int i=0;i<m;i++) printf("%d %d %d
",es[i].u,es[i].v,es[i].cost);
46     long long sum=0;
47     int count=0;
48     for(int i=0;i<m;i++)
49     {
50         edge e=es[i];
51         if(find(e.u)!=find(e.v))
52         {
53             unite(e.u,e.v);
54             count++;
55             sum+=e.cost;
56         }
57     }
58     if(count!=n-1) sum=-1;
59     return sum;
60 }
61 int main()
62 {
63     //freopen("a.txt","r",stdin);
64     int a,b,c;
65     while(~scanf("%d%d",&n,&m))
66     {
67         init();
68         for(int i=0;i<m;i++)
69         {
70             scanf("%d%d%d",&a,&b,&c);
71             es[i]=edge(a,b,c);
72         }
73         printf("%lld
",kruskal());
74     }
75     return 0;
76 }

http://poj.org/problem?id=2395

bessie打算去其他农场，这里总共有N个农场，她开始在1号农场，然后有M条双向连通的路，并且可能还有重边，所有的农场都至少有一条路和1号农场相连。去其他农场需要水所以需要一个水袋，但是不知道需要准备多大的袋子，已知每走一公里就会消耗一单元的水，并且每到一个农场就可以补充水，让你找出任意两个农场中距离最长的路，这样就能知道最少需要准备多大的袋子来装水。

扯了这么多就是在最小生成树中找出路径最长的那一条边，比上面一题还简单。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct edge
 7 {
 8     int u,v,cost;
 9     edge() {}
10     edge(int x,int y,int z)
11     {
12         u=x;
13         v=y;
14         cost=z;
15     }
16     bool operator <(const edge& a) const
17     {
18         return cost<a.cost;
19     }
20 };
21 
22 edge es[10010];
23 int par[2010];
24 int n,m;
25 void init()
26 {
27     for(int i=1;i<=n;i++) par[i]=i;
28 }
29 
30 int find(int x)
31 {
32     return x==par[x]?x:par[x]=find(par[x]);
33 }
34 
35 void unite(int x,int y)
36 {
37     x=find(x);
38     y=find(y);
39     if(x!=y) par[x]=y;
40 }
41 
42 long long kruskal()
43 {
44     sort(es,es+m);
45     //for(int i=0;i<m;i++) printf("%d %d %d
",es[i].u,es[i].v,es[i].cost);
46     long long sum=0;
47     for(int i=0;i<m;i++)
48     {
49         edge e=es[i];
50         if(find(e.u)!=find(e.v))
51         {
52             unite(e.u,e.v);
53             if(e.cost>sum) sum=e.cost;
54         }
55     }
56     return sum;
57 }
58 int main()
59 {
60     //freopen("a.txt","r",stdin);
61     int a,b,c;
62     while(~scanf("%d%d",&n,&m))
63     {
64         init();
65         for(int i=0;i<m;i++)
66         {
67             scanf("%d%d%d",&a,&b,&c);
68             es[i]=edge(a,b,c);
69         }
70         printf("%lld
",kruskal());
71     }
72     return 0;
73 }