Conscription POJ - 3723

Myth丶恋晨 2022-12-02 01:11 140阅读 0赞

题目本身不难，但好像题意有点难懂。

给了N个男生，M个女生。要招募这（N+M）个人，需要花费1000\*（N+M）。但现在男生和女生直接可以有一种联系，这种联系的数值为di，如果你想招募x，并且y与x 相连同时y已经被招募（其实即使y没有被招募，你也可以选择先花10000招募y，然后y就变成被招募状态了），那么你可以减少di元。

因此，我们可以将招募的人统一用并查集合并，如果某条边的两个点x,y，不在同一集合时，代表这条边的值可以被减少。

所以，最佳的做法就是每次选择权重最大的边，即用最小生成树的算法来做。

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    #include <queue>
    #include <map>
    #include <vector>
    #include <set>
    #include <string>
    #include <math.h>
    #include <stack>
    using namespace std;
    const int maxn=1e5+7;
    #define INF 0x3f3f3f3f
    typedef pair<int,int> P;
    int M,N,R;
    int ans;
    int f[maxn];
    struct Point
    {
        int u,v,cost;
        Point(int u_,int v_,int c)
        {
            u = u_;
            v = v_;
            cost = c;
        }
        Point(){
    
        }
    };
    Point edge[maxn];
    bool cmp(Point a,Point b)
    {
        return a.cost<b.cost;
    }
    void init(int n)
    {
        for(int i=0;i<n;i++)
        {
            f[i] = i;
        }
    }
    int Find(int x)
    {
        if(f[x]==x) return f[x];
        else return f[x]=Find(f[x]);
    }
    bool same(int x,int y)
    {
        return Find(x)==Find(y);
    }
    void com(int x,int y)
    {
        int fx =Find(x),fy = Find(y);
        if(fx==fy) return;
        f[fy] = fx;
    }
    void krustal()
    {
        sort(edge,edge+R,cmp);
        init(N+M);
        ans=0;
        for(int i=0;i<R;i++)
        {
            int x=edge[i].u,y=edge[i].v;
            //cout<<x<<" "<<y<<endl;
            if(same(x,y)==0)
            {
                ans+=edge[i].cost;
                com(x,y);
            }
        }
    }
    int T;
    int x[maxn],y[maxn],d[maxn];
    int main()
    {
        #ifndef ONLINE_JUDGE
            freopen("in.txt","r",stdin);
            freopen("out.txt","w",stdout);
        #endif
        cin>>T;
        while(T--)
        {
            cin>>N>>M>>R;
            //cout<<N<<" "<<M<<" "<<R<<endl;
            for(int i=0;i<R;i++)
            {
                scanf("%d%d%d",&x[i],&y[i],&d[i]);
            }
            for(int i=0;i<R;i++)
            {
                edge[i].u=x[i];
                edge[i].v=y[i]+N;
                edge[i].cost = -d[i];
            }
            krustal();
            cout<<10000*(N+M)+ans<<endl;
        }
        return 0;
    }