牛客练习赛61 C 四个选项（并查集、DP、排列组合）难度⭐⭐⭐

链接：https://ac.nowcoder.com/acm/contest/5026/C

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

众所周知，高考数学中有一个题目是给出12个单项选择，每一个选择的答案是 $A ， B ， C ， D$ 中的一个。网上盛传答案存在某种规律，使得蒙对的可能性大大增加。于是今年老师想让你安排这12个题的答案。但是他有一些条件，首先四个选项的数量必须分别为 $n a ， n b ， n c ， n d$ 。其次有 m 个额外条件，分别给出两个数字 $x ， y$ ，代表第 x 个题和第 y 个题的答案相同。现在你的老师想知道，有多少种可行的方案安排答案。
输入描述:
$第一行五个非负整数 n a ， n b ， n c ， n d ， m ，保证 n a + n b + n c + n d = 12 ， 0 \leq m \leq 1000 。接下来 m 行每行两个整数 x ， y （ 1 \leq x, y \leq 12 ）代表第 x 个题和第 y 个题答案必须一样$ 。
输出描述:
仅一行一个整数，代表可行的方案数。

示例1

输入

3 3 3 3 0

输出

简单的DP

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=15;
const ll INF=1e10+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;

ll n,m,dp[N][N][N][N];
ll fa[N],sum,sz[N],size[N];
ll a[N],na,nb,nc,nd,cnt;

inline void init()
{
    over(i,0,11)
        fa[i]=i,size[i]=1;
}

inline ll finds(ll x)
{
    return fa[x]==x?x:fa[x]=finds(fa[x]);
}
inline void unite(ll x,ll y)
{
    ll a=finds(x),b=finds(y);
    if(a!=b){
        if(a>b)swap(a,b);
        fa[b]=a,size[a]+=size[b];
    }
}
int main()
{
    init();//服了，已经多少次了，写了init不写init
    scanf("%lld%lld%lld%lld%lld",&na,&nb,&nc,&nd,&m);
    while(m--)
    {
        ll a,b;
        scanf("%lld%lld",&a,&b);
        a--,b--;
        unite(a,b);
    }
    over(i,0,12-1)
    {
        if(fa[i]==i)//独立的题
            sz[cnt++]=size[i];
    }
    dp[0][0][0][0]=1;
    for(int i=0;i<cnt;++i){
        for(int a=0;a<=na&&a<=sum;++a){
            for(int b=0;b<=nb&&a+b<=sum;++b){
                for(int c=0;c<=nc&&a+b+c<=sum;++c)
                {
                    int d=sum-a-b-c;
                    if(d>nd)continue;
                    if(a+sz[i]<=na)
                        dp[i+1][a+sz[i]][b][c]+=dp[i][a][b][c];
                    if(b+sz[i]<=nb)
                        dp[i+1][a][b+sz[i]][c]+=dp[i][a][b][c];
                    if(c+sz[i]<=nc)
                        dp[i+1][a][b][c+sz[i]]+=dp[i][a][b][c];
                    if(d+sz[i]<=nd)
                        dp[i+1][a][b][c]+=dp[i][a][b][c];
                }
            }
        }
        sum+=sz[i];
    }
    printf("%lld\n",dp[cnt][na][nb][nc]);
    return 0;
}

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧