[BZOJ3390]&&[Usaco2004 Dec]Bad Cowtractors 牛的报复

2014-09-18
竞赛题解 / 图论
BZOJUSACO最小生成树

描述 Description

奶牛贝茜被雇去建设 N(2≤N≤1000) 个牛棚间的互联网．她已经勘探出 M(1≤M≤20000) 条可建的线路，每条线路连接两个牛棚，而且会苞费 C(1≤C≤100000)．农夫约翰吝啬得很，他希望建设费用最少甚至他都不想给贝茜工钱． 贝茜得知工钱要告吹，决定报复．她打算选择建一些线路，把所有牛棚连接在一起，让约翰花费最大．但是她不能造出环来，这样约翰就会发现．

输入格式 InputFormat

第 1 行：N，M.

第 2 到 M+1 行：三个整数，表示一条可能线路的两个端点和费用.

输出格式 OutputFormat

最大的花费．如果不能建成合理的线路，就输出 - 1

样例输入 SampleInput

10 20
1 9 34
1 8 94
2 7 80
9 10 67
7 6 98
8 4 61
7 9 24
9 7 20
10 1 59
2 5 58
7 5 66
10 7 35
3 9 92
5 7 13
3 5 68
10 4 51
1 3 70
6 1 56
8 1 18
8 2 84

样例输出 SampleOutput

714

BZOJ 3390

代码 Code

最大生成树。最后判断是否合理线路即为是否所有点的最远祖先为同一个人。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
inline void read(int &x)
{
    x=0;char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
struct edge
{
    int u,v,w;
    bool operator < (const edge& temp) const
    {
        return (w!=temp.w)?(w<temp.w):((u!=temp.u)?(u<temp.u):(v<temp.v));
    }
}e[40005];
int fa[1005];
int cnt,ans;
int getfa(int s)
{
    if (fa[s]==s) return s;
    fa[s]=getfa(fa[s]);
    return fa[s];
}
int main()
{
    read(n);read(m);
    cnt=0;
    for (i=1;i<=m;i++)
    {
        read(x);read(y);read(z);
        e[++cnt].u=x;e[cnt].v=y;e[cnt].w=z;
    }
    ans=0;
    sort(e+1,e+cnt+1);
    for (i=1;i<=n;i++) fa[i]=i;
    for (i=cnt;i>=1;i--) if (getfa(e[i].u)!=getfa(e[i].v))
    {
        fa[getfa(e[i].u)]=e[i].v;
        ans+=e[i].w;
    }
    t=getfa(1);
    for (i=2;i<=n;i++) if (getfa(i)!=t)
    {
        printf("%d\n",-1);
        return 0;
    }
    printf("%d\n",ans);
    return 0;
}