POJ-2377 Bad Cowtractors---最大生成树

题目链接：

https://vjudge.net/problem/POJ-2377

题目大意：

给一个图，求最大生成树权值，如果不连通输出-1

思路：

kruskal算法变形，sort按边从大到小排序，就可以了，或者用一个maxn-w[u][v]作为<u, v>边的权值，直接用原来的kruskal算法求出权值，然后用maxn*(n-1)-sum就为最大生成树权值

 #include<iostream>

 #include<vector>

 #include<queue>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<set>

 #include<map>

 #include<cmath>

 using namespace std;

 typedef pair<int, int> Pair;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 int T, n, m;

 const int maxn = 2e4 + ;

 struct edge

 {

     int v, u, w;

     bool operator < (const edge a)const

     {

         return w > a.w;

     }

 };

 edge e[maxn];

 int pa[maxn];

 int Find(int x)

 {

     return x == pa[x] ? x : pa[x] = Find(pa[x]);//路径压缩

 }

 void kruskal()

 {

     for(int i = ; i <= n; i++)pa[i] = i;

     sort(e, e + m);

     ll ans = ;

     for(int i = ; i < m; i++)

     {

         ll v = e[i].v, u = e[i].u, w = e[i].w;

         ll x = Find(v), y = Find(u);

         if(x != y)

         {

             pa[x] = y;

             ans += w;

         }

     }

     int tot = ;

     for(int i = ; i <= n; i++)//判断是否联通，是否只有一个父节点是自己的点

     {

         if(pa[i] == i)tot++;

     }

     if(tot > )cout<<"-1"<<endl;

     else cout<<ans<<endl;

 }

 int main()

 {

     cin >> n >> m;

     for(int i = ; i < m; i++)cin >> e[i].v >> e[i].u >> e[i].w;

     kruskal();

 }

 #include<iostream>

 #include<vector>

 #include<queue>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<set>

 #include<map>

 #include<cmath>

 using namespace std;

 typedef pair<int, int> Pair;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 int T, n, m;

 const int maxn = 2e4 + ;

 struct edge

 {

     int v, u, w;

     bool operator < (const edge a)const

     {

         return w < a.w;

     }

 };

 edge e[maxn];

 int pa[maxn];

 int Find(int x)

 {

     return x == pa[x] ? x : pa[x] = Find(pa[x]);//路径压缩

 }

 void kruskal()

 {

     for(int i = ; i <= n; i++)pa[i] = i;

     sort(e, e + m);

     ll ans = ;

     for(int i = ; i < m; i++)

     {

         ll v = e[i].v, u = e[i].u, w = e[i].w;

         ll x = Find(v), y = Find(u);

         if(x != y)

         {

             pa[x] = y;

             ans += w;

         }

     }

     int tot = ;

     for(int i = ; i <= n; i++)//判断是否联通，是否只有一个父节点是自己的点

     {

         if(pa[i] == i)tot++;

     }

     ans = 100000LL * ((ll)n - ) - ans;

     if(tot > )cout<<"-1"<<endl;

     else cout<<ans<<endl;

 }

 int main()

 {

     cin >> n >> m;

     for(int i = ; i < m; i++)

     {

         cin >> e[i].v >> e[i].u >> e[i].w;

         e[i].w =  - e[i].w;

     }

     kruskal();

 }