HDU 5305 Friends(2015多校联合)

发表于   |  

题目链接：

戳我

题目大意：

有 n个人，m对朋友关系，朋友之间可以选择成为 在线朋友 或者 离线朋友，每个人都想有相同数目的 在线朋友 和 离线朋友。（比如一个人有 x 个在线朋友，那么他必须有 x 个离线朋友）但是不同的人 x 可以不同。求有多少种方案可以满足他们的要求。

样例解释

2 两个测试用例
3 3 三个人，三对朋友关系
1 2 1 2 是朋友，他们可以选择成为离线或者在线朋友
2 3 2 3 是朋友，他们可以选择成为离线或者在线朋友
3 1 3 4 是朋友，他们可以选择成为离线或者在线朋友
4 4 同理
1 2
2 3
3 4
4 1

解题思路

此处输入图片的描述

代码

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
//Author LJH
//www.cnblogs.com/tenlee
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define clc(a, b) memset(a, b, sizeof(a))
using namespace std;

const int inf = 0x3f;
const int INF = 0x3f3f3f3f;
const int maxn = 10;
int du_on[maxn], du_off[maxn], g[maxn][maxn];
int n, m, ans;

void dfs(int x, int y)
{
    if(x > n) ans++;
    else if(y > n)
    {
        if(du_on[x] != du_off[x]) return; //如果一个人的在线朋友和离线朋友不相等,直接退出，
        dfs(x+1, x+2);
    }
    else 
        if(g[x][y]) //枚举
        {
            du_on[x]++; du_on[y]++;//在线朋友个数加一
            dfs(x, y+1);
            du_on[x]--; du_on[y]--;//还原回来，因为下面的dfs可能会用到

            du_off[x]++; du_off[y]++;
            dfs(x, y+1);
            du_off[x]--; du_off[y]--;
        }
        else 
            dfs(x, y+1);

}

int main()
{
    int T, x, y;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d %d", &n, &m);
        clc(du_on, 0);
        clc(du_off, 0);
        clc(g, 0);
        while(m--)
        {
            scanf("%d %d", &x, &y);
            g[x][y] = g[y][x] = 1;
        }
        ans = 0;
        dfs(1, 2);
        printf("%d\n", ans);
    }
}