hdu5305and杭电多校集训第二题（1006题 friend）

题目大意：有n个人，m个关系，其中关系有两种，问你能找到多少种方式，使得每个人的两种关系都相等。

解题思路：图的边的枚举+剪枝+回朔，n个人看做n个点，m个关系看成m条边，两种关系看做两种其他度，边的枚举（用递归来枚举，一开始我用二进制，果断TLE），剪枝的话，是每次枚举一条边，就有两个点的度数+1，统计下当前的其他度数，不能超过它本身的度数（这个就是图论里的度数）的一半，超过一半return

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=50;
int u[maxn],v[maxn],tot[15],r1[15],r2[15],t,n,m,ans;
int dfs(int num)
{
    if(num == m+1)
    {
        for(int i = 1; i <= n; i++)
        {
            if(r1[i] != r2[i])

                return 0;
        }
        ans++;
        return 1;
       }
        int x=u[num],y=v[num];
        if(r1[x]+1<=tot[x]/2&&r1[y]+1<=tot[y]/2)
        {
                r1[x]++;
                r1[y]++;
                dfs(num+1);
                 r1[x]--;
                 r1[y]--;
        }
        if(r2[x]+1<=tot[x]/2&&r2[y]+1<=tot[y]/2)
        {
                r2[x]++;
                r2[y]++;
                dfs(num+1);
                r2[x]--;
                r2[y]--;
        }
}
int main()
{
        scanf("%d",&t);
        while(t--)
        {
                ans=0;
                memset(tot,0,sizeof(tot));
                memset(r1,0,sizeof(r1));
                memset(r2,0,sizeof(r2));
                scanf("%d%d",&n,&m);
                for(int i=1;i<=m;i++)
                {
                    scanf("%d%d",&u[i],&v[i]);
                    tot[u[i]]++;
                    tot[v[i]]++;
                }
                int flag=0;
                for(int i=1;i<=n;i++)
                {
                    if(tot[i]%2!=0) flag=1;
                }
                dfs(1);
                if(flag)  {printf("0n");continue;}
                printf("%dn",ans);
        }
        return 0;
}

最后

以上就是爱笑黑裤为你收集整理的hdu5305and杭电多校集训第二题（1006题 friend）的全部内容，希望文章能够帮你解决hdu5305and杭电多校集训第二题（1006题 friend）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。