POJ 3723 Conscription(最大生成树)

POJ 3723 Conscription(最大生成树)

http://poj.org/problem?id=3723

题意:

要招n女，m男，每招一个人需要10000元，但是有一些男女有关系，代价为d，比如第i个女和第j个男有代价为d的关系，那么他们任意一个如果已经被招，则招另一个只需10000 - d元，问最少要用多少元招完这n女m男。

分析:

因为一共n+m个人,我们本来需要换(n+m)*10000元的.但是可以使用关系招聘,所以我们最好的情况是:除了第一个人外,之后的每个人我们都通过关系招聘进来且总关系的权值和最大.那么我们招聘的成本就最小了.

把每个人看成一个点,人与人之间的关系d看成权值为d的边.如果人与人之间原来没有关系,那么它们之间有一条权值为0的边.这样构成了一个无向图.

其实现在就是要我们选(n+m-1)条边(因为最多使用n+m-1次关系招聘)使得这n+m个点是一个连通图(其实就是生成树,假设我们n+m-1条边连接的图有两个连通分量,那么我们肯定有2个人不是通过关系招聘的.且我们肯定浪费了一条边,因为这条边没有起到关系优惠的作用,我们还不如用一条权值为0的关系边把这两个分量连通起来呢)且要求这n+m-1条关系边的权值和最大(权值和最大,得到的招聘优惠就越多).

注意:如果原题给的关系边不足以连通图,那么我们可以任意选两点连一条权值为0的边.(权值为0,即代表无优惠,但是还是有关系的)

最终答案== (n+m)*10000-最大生成树的权值

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn= 20000+10;
const int maxm= 50000+10;

struct Edge
{
    int u,v,dist;
    Edge(){}
    Edge(int u,int v,int dist):u(u),v(v),dist(dist){}
    bool operator<(const Edge &rhs)const
    {
        return dist > rhs.dist;//让边从大到小排列
    }
};

struct Kruskal
{
    int n,m;
    Edge edges[maxm];
    int fa[maxn];
    int findset(int x){ return fa[x]==-1?x:fa[x]=findset(fa[x]); }

    void init(int n)
    {
        this->n=n;
        m=0;
        memset(fa,-1,sizeof(fa));
    }

    void AddEdge(int u,int v,int dist)
    {
        edges[m++]=Edge(u,v,dist);
    }

    int kruskal()
    {
        int sum=0,cnt=0;
        sort(edges,edges+m);

        for(int i=0;i<m;i++)
        {
            int u=edges[i].u, v=edges[i].v;
            if(findset(u) != findset(v))
            {
                fa[findset(u)] = findset(v);
                sum += edges[i].dist;
                if(++cnt>=n-1) break;
            }
        }
        return sum; //就算cnt<n-1图不连通,也返回sum.
                    //因为还有权值为0的关系,我没有添加进来
    }
}KK;

int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        int n,m,r;
        scanf("%d%d%d",&n,&m,&r);
        KK.init(n+m);
        while(r--)
        {
            int u,v,d;
            scanf("%d%d%d",&u,&v,&d);
            KK.AddEdge(u,v+n,d);
        }
        printf("%d\n",(n+m)*10000-KK.kruskal());
    }
    return 0;
}