hdu5305

95 阅读 0 评论 63 点赞

我是靠谱客的博主完美鱼，这篇文章主要介绍hdu5305，现在分享给大家，希望可以做个参考。

题目名称：Friends

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5305

题意：给定n个人，m对朋友关系，朋友关系可以选择online聊天，也可以选择offline，对于每个人，他选择的online和offline的朋友相同（比如拥有x个online，就得拥有x个offline），问全部人满足有多少种情况？只要一个选择不同，视为不同情况。

思路（hdu的题解）：由于总点数很少，我们考虑暴力，但总的边数有8*7/2=28，所以会TLE，一个点的度数为奇数时，答案肯定为0，每个点为偶数时，总边数最多为8*6/2=24，还是一个较大的数字。最后一个优化是搜索一个点到最后一条边时不用枚举，因为已经确定了。也就是说搜索边数少n-1，所以只要搜索17条边，暴力就可以了，，

搜索他给的那些边，然后可以为online或者offline，最后判断每个点的online朋友和offline朋友是否相等就行了，相等就总数加一

代码如下：

复制代码

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int d1[10],d2[10],sum[10];  //d1表示online,d2表示offline
int n,m;
int ans=0,a[30],b[30];
int judge()     //判断online和offline相等
{
    for(int i=1;i<=n;i++)
    {
        if(d1[i]!=d2[i])
            return 0;
    }
    return 1;
}
void dfs(int num)     //num表示第几组关系
{
    if(num==m+1)
    {
        if(judge())
            ans++;
        return ;
    }
    int x=a[num],y=b[num];
    if((d1[x]<sum[x]/2)&&(d1[y]<sum[y]/2))   //假设该边为online
    {
        d1[x]++;
        d1[y]++;
        dfs(num+1);
        d1[x]--;        //记得修改的边要及时修改回来
        d1[y]--;
    }
    if((d2[x]<sum[x]/2)&&(d2[y]<sum[y]/2))
    {
        d2[x]++;
        d2[y]++;
        dfs(num+1);
        d2[x]--;
        d2[y]--;
    }
}
int main()
{
    int t;
    while(scanf("%d",&t)!=EOF)
    {
        while(t--)
        {
            memset(d1,0,sizeof(d1));
            memset(d2,0,sizeof(d2));
            memset(sum,0,sizeof(sum));
            scanf("%d%d",&n,&m);
            for(int i=1;i<=m;i++)
            {
                scanf("%d%d",&a[i],&b[i]);
                sum[a[i]]++;
                sum[b[i]]++;
            }
            ans=0;
            int ok=1;
            for(int i=1;i<=n;i++)    //为奇数时说明不成立
            {
                if(sum[i]&1)
                {
                    ok=0;
                    break;
                }
            }
            if(ok)
            {
                dfs(1);
                printf("%dn",ans);
            }
            else
                printf("0n");
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int d1[10],d2[10],sum[10];  //d1表示online,d2表示offline
int n,m;
int ans=0,a[30],b[30];
int judge()     //判断online和offline相等
{
    for(int i=1;i<=n;i++)
    {
        if(d1[i]!=d2[i])
            return 0;
    }
    return 1;
}
void dfs(int num)     //num表示第几组关系
{
    if(num==m+1)
    {
        if(judge())
            ans++;
        return ;
    }
    int x=a[num],y=b[num];
    if((d1[x]<sum[x]/2)&&(d1[y]<sum[y]/2))   //假设该边为online
    {
        d1[x]++;
        d1[y]++;
        dfs(num+1);
        d1[x]--;        //记得修改的边要及时修改回来
        d1[y]--;
    }
    if((d2[x]<sum[x]/2)&&(d2[y]<sum[y]/2))
    {
        d2[x]++;
        d2[y]++;
        dfs(num+1);
        d2[x]--;
        d2[y]--;
    }
}
int main()
{
    int t;
    while(scanf("%d",&t)!=EOF)
    {
        while(t--)
        {
            memset(d1,0,sizeof(d1));
            memset(d2,0,sizeof(d2));
            memset(sum,0,sizeof(sum));
            scanf("%d%d",&n,&m);
            for(int i=1;i<=m;i++)
            {
                scanf("%d%d",&a[i],&b[i]);
                sum[a[i]]++;
                sum[b[i]]++;
            }
            ans=0;
            int ok=1;
            for(int i=1;i<=n;i++)    //为奇数时说明不成立
            {
                if(sum[i]&1)
                {
                    ok=0;
                    break;
                }
            }
            if(ok)
            {
                dfs(1);
                printf("%dn",ans);
            }
            else
                printf("0n");
        }
    }
    return 0;
}