hdu 6795 Little W and Contest 并查集+排列组合

题意：

t组输入，有n个人，刚开始谁也不认识谁。每一个人有一个权值w[i]（1<=w[i]<=2），你要挑选3个互相不认识的人组成一个队，且要保证3个人权值之和大于等于5(也就意味着最少要有权值为2的人)

为你能找到多少个满足题意得队伍

然后给你n-1个关系，每个关系输入x y

这表示x和y认识了，而且如果z认识y，那么x也认识z。即关系具有传递性

然后在输出你还能找到多少个满足题意得队伍（这样循环n-1次）

题解：

因为关系有传递性，所以如果x和y认识，我们可以让x所在这个集合和y所在这个集合合并成一个集合，也就是这里用到了并查集

我们开始统计一下权值为1得总人数为cnt1，权值为2得总人数为cnt2

那么最开始n个人都不认识的时候能找到sum个满足题意的队伍，下面算式用排列组合表示：C_cnt2³+C²_cnt2*cnt1

sum=cnt2*(cnt2-1)*(cnt2-2)/6+cnt2*(cnt2-1)*cnt1/2;

用s1[i]表示第i个集合有s1[i]个人的权值为1

用s2[i]表示第i个集合有s2[i]个人的权值为2

如果x 合并入 y 集合，那么要重新统计一下s1[y]和s2[y]，而且一些队伍不能满足题意了，要减去不满足题意得队伍

代码：

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <vector>

#include <map>

#include <queue>

#include <stack>

#include <set>

#include <ctime>

#include <cstring>

#include <cstdlib>

#include <math.h>

#include<map>

using namespace std;

typedef long long ll;

const int MOD=1e9+7;

const int maxn = 1e5 + 5;

ll v[maxn],w[maxn];

ll n,s[maxn],s2[maxn],cnt1,cnt2,sum;

ll finds(ll x)

{

    if(v[x]!=x)

    {

        ll y=finds(v[x]);

        v[x]=y;

        return y;

    }

    return x;

}

void solve(ll x,ll y)

{

    ll fx=finds(x);

    ll fy=finds(y);

    sum=sum-(s2[fx]*s2[fy]*(cnt2-s2[fx]-s2[fy]));  // 2 2 2，意思：从s2[fx]中选择一个2权值的人，从s2[fy]中选择一个2权值的人，从剩下不再s2[fx]和s2[fy]集合里面，且权值为2的人中选择一个

    sum=sum-(s2[fx]*s2[fy]*(cnt1-s[fx]-s[fy]));    // 2 2 1

    sum=sum-(s2[fx]*s[fy]*(cnt2-s2[fx]-s2[fy]));  // 2 1 2

    sum=sum-(s[fx]*s2[fy]*(cnt2-s2[fx]-s2[fy]));   // 1 2 2

    v[fx]=fy;

    s[fy]+=s[fx];

    s2[fy]+=s2[fx];

    printf("%lld\n",sum%MOD);

}

int main()

{

    ll t;

    scanf("%lld",&t);

    while(t--)

    {

        cnt1=cnt2=sum=0;

        memset(s,0,sizeof(s));

        memset(s2,0,sizeof(s2));

        scanf("%lld",&n);

        for(ll i=1;i<=n;++i)

        {

            v[i]=i;

            scanf("%lld",&w[i]);

            if(w[i]==1) cnt1++,s[i]++;

            else cnt2++,s2[i]++;

        }

        sum=cnt2*(cnt2-1)*(cnt2-2)/6+cnt2*(cnt2-1)*cnt1/2;

        printf("%lld\n",sum%MOD);

        for(ll i=1;i<n;++i)

        {

            ll x,y;

            scanf("%lld%lld",&x,&y);

            solve(x,y);

        }

    }

    return 0;

}

巴特西

hdu 6795 Little W and Contest 并查集+排列组合

最新文章

热门文章