POJ 2377 Bad Cowtractors

這是先前做的幾道最小生成樹的題目，基本都是裸題。

題意：求最大生成樹

由於數據比較水，用prime和krusical都可以。我是用krusical做的

 #include<iostream>   
#include<cstdio>   
#include<cmath>   
#include<cstring>   
#include<algorithm>   
using namespace std;  
int n,m,f[1010];  
struct node  
{  
    int x,y,s;  
}e[20010];  
bool cmp(node s, node v)  
{  
    return s.s>v.s;  
}  
int find(int x)  
{  
    if (x==f[x]) return x;  
    f[x]=find(f[x]);  
    return f[x];  
}  
void krusical()  
{  
    int i,t=0,ans=0;  
    for (i=0; i<m; i++)  
    {  
        int x=find(e[i].x);  
        int y=find(e[i].y);  
        if (x!=y)  
        {  
            ans+=e[i].s;  
            f[y]=f[x];  
            t++;  
        }  
        if (t==n-1) break;  
    }  
    if (t==n-1) cout<<ans<<endl;  
    else cout<<"-1"<<endl;  
}  
int main ()  
{  
    cin>>n>>m;  
    int i,j;  
    for (i=1; i<=n; i++)  
        f[i]=i;  
    for (i=0; i<m; i++)  
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].s);  
    sort(e,e+m,cmp);  
    krusical();  
    return 0;  
}  

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,f[1010];
struct node
{
    int x,y,s;
}e[20010];
bool cmp(node s, node v)
{
    return s.s>v.s;
}
int find(int x)
{
    if (x==f[x]) return x;
    f[x]=find(f[x]);
    return f[x];
}
void krusical()
{
    int i,t=0,ans=0;
    for (i=0; i<m; i++)
    {
        int x=find(e[i].x);
        int y=find(e[i].y);
        if (x!=y)
        {
            ans+=e[i].s;
            f[y]=f[x];
            t++;
        }
        if (t==n-1) break;
    }
    if (t==n-1) cout<<ans<<endl;
    else cout<<"-1"<<endl;
}
int main ()
{
    cin>>n>>m;
    int i,j;
    for (i=1; i<=n; i++)
        f[i]=i;
    for (i=0; i<m; i++)
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].s);
    sort(e,e+m,cmp);
    krusical();
    return 0;
}