hdu 5305 Friends

タイトルリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=5305
問題解決の考え方:
総点数が少ないので、暴力を考えています.しかし総辺数は(8*7)/2=28であるため,各辺を直接列挙した状態はTLEに違いない.また、1つの点が存在する度数が奇数である場合、最終的な答えは0であり、各点の度数が偶数である場合、総辺数は最大(8*6)/2=24であり、かなり大きな数字であることに気づいた.最後の最適化は、1つの点を検索するたびに、最後のエッジに列挙される状態は列挙されず、このエッジが黒であるか白であるかはすでに決定されている(前に選択されたエッジの白黒状態に基づいて)、つまり検索する必要があるエッジ数がn−1減少すると、最大17エッジを検索するだけである.これでストレスなく解けるようになりました..
ACコード:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n,m;
int a[30],b[30],cnt;
int sum[10],on[10],off[10];//sum        ，on      online，off      offline

bool judge(){
    for(int i = 1; i <= n; i++){
        if(on[i] != off[i])
            return false;
    }
    return true;
}

void dfs(int cur){
    if(cur == m+1){
        if(judge()){
            cnt++;
            return;
        }
    }
    int x = a[cur], y = b[cur];
    if(on[x] < sum[x]/2 && on[y] < sum[y]/2){
        on[x]++;
        on[y]++;
        dfs(cur+1);
        on[x]--;
        on[y]--;
    }
    if(off[x] < sum[x]/2 && off[y] < sum[y]/2){
        off[x]++;
        off[y]++;
        dfs(cur+1);
        off[x]--;
        off[y]--;
    }
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(on,0,sizeof(on));
        memset(off,0,sizeof(off));
        memset(sum,0,sizeof(sum));
        int flag = 1;
        cnt = 0;
        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]]++;
        }
        for(int i = 1; i <= n; i++){
            if(sum[i] % 2){
                flag = 0;
                break;
            }
        }
        if(flag){
            dfs(1);
            printf("%d
",cnt);
        }
        else
            printf("0
");
    }
    return 0;
}