1342. 【南海2009初中】cowtract（网络） (Standard IO)

题目：

Bessie受雇来到John的农场帮他们建立internet网络。农场有 N (2<= N <= 1,000)牛棚，编号为1..N。John之前已经勘测过，发现有 M (1<= M <= 20,000)条可能的连接线路，一条线路是连接某两个牛棚的。每条可能的线路都有一个建设费用 C (1<= C <=100,000)。John当然想花尽量少的钱，甚至克扣Bessie的工钱。

Bessie发现了这点，很生气，决定给John捣乱。她要选择一些线路组成网，但费用却尽可能大。当然网络要能正常工作，也就是任意两个牛棚之间都是相互可以连通的，并且网络上不能有环，不然John会很容易发现的。

请计算组建这种网络最多可能的费用。

输入：

第一行：两个整数 N M

下面M行：每行3个整数 A，B，C。表示一个可能的线路要连接A、B两个牛棚，费用是C。

输出：

只一行，一个整数，即花费最大的费用。如果不可能连接通所有牛棚，输出-1。

样例：

输入输出

5 8 42
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17

思路：

思路很简单，典型的一道“最小”生成树只需要将“<”改至“>”，也就是说还是可以照常用Keuskal算法。话不多说上代码。

CODE

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int fa[];

int n,m,ans,num;

struct cow

{

    int bb,son,money;

};

cow tree[];

int find(int x)

{

    if(fa[x]!=x)

    fa[x]=find(fa[x]);

    return fa[x];

}

void add(int x,int y)

{

    fa[fa[x]]=fa[y];

}

bool cmp(cow x,cow y)

{

    return x.money>y.money;

}

int main()

{

    cin>>n>>m;

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

    fa[i]=i;

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

    {

        cin>>tree[i].bb>>tree[i].son>>tree[i].money;

    }

    sort(tree+,tree++m,cmp);

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

    {

        if(find(tree[i].bb)!=find(tree[i].son))

        {

            add(tree[i].bb,tree[i].son);

            ans=ans+tree[i].money;

            num++;

        }

    }

    if(num==n-)

        {

            cout<<ans;

            return ;

        }

        else

        {

            cout<<-;

            return ;

        }

}

巴特西

普及C组第四题（8.2）

1342. 【南海2009初中】cowtract（网络） (Standard IO)

题目：

输入：

输出：

样例：

完结撒花！！！

最新文章

热门文章