POJ3723（最小生成树，负权）

题目描述

温迪有一个国家，他想建立一支军队来保护他的国家。他收留了N个女孩和M个男孩，想把她们收留成他的士兵。征兵无特权，必须交纳一万元。女孩和男孩之间有一些关系，温迪可以利用这些关系来降低他的成本。如果X女孩和Y男孩有D关系，并且其中一个已经被收集，Windy可以用10000-D人民币收集另一个。现在考虑到男孩和女孩之间的所有关系，你的任务是找到风必须支付的最少的钱。注意，收集一个士兵时只能使用一个关系。Input

输入的第一行是测试用例的数量。每个测试用例的第一行包含三个整数，n、m和r。然后R行，每个包含三个整数Xi，Yi和DI。每个测试用例前都有一个空白行。

1 ≤ N, M ≤ 10000
0 ≤ R ≤ 50,000
0 ≤ x_i < N
0 ≤ y_i < M
0 < d_i < 10000

Output

For each test case output the answer in a single line.

Sample Input

Sample Output

71071

54223
代码如下，参考挑战程序设计竞赛

#include<iostream>

#include<cstdio>

#include<vector>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

#define ull unsigned long long

#define ll long long

const int maxn=5e4+;

int par[maxn];

int rank1[maxn],n,m,r;

void init(int n) //初始化

{

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

    {

        par[i]=i;

        rank1[i]=;

     }

}

int find(int x)

{

    if(par[x]==x)

    {

        return x;

    }

    else

    {

        return par[x]=find(par[x]);

    }

}

void unite(int x,int y)

{

    x=find(x);

    y=find(y);

    if(x==y)

    return ;

    if(rank1[x]<rank1[y])

    {

        par[x]=y;

    }

    else

    {

        par[y]=x;

    }

    if(rank1[x]==rank1[y])

    rank1[x]++;

}

struct edge{

    int x,y,cost;

}e[];

bool cmp(const edge e1,const edge e2)

{

    return e1.cost<e2.cost;

}

ll kruskal()

{

    ll res=;

    sort(e+,e+r+,cmp);

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

    {

        edge e1=e[i];

        if(find(e1.x)!=find(e1.y))

        {

            unite(e1.x,e1.y);

            res=res+e1.cost;

        }

    }

    return res;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d%d",&n,&m,&r);

        init(n+m);

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

        {

            scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].cost);

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

            e[i].y=e[i].y+n;

        }

        printf("%lld\n",10000LL*(n+m)+kruskal());

    }

    return ;

}

巴特西

POJ3723（最小生成树，负权）

最新文章

热门文章