题解 | #ACM Battle#

一题不怎么明显的爆搜，刚刚看到题还以为是点覆盖，但是发现转不成二分树，DP也没什么思路，最后只能爆搜。搜点不是很容易，试着搜边。用vis[]
数组记录了某点是否被滴过，在搜边时如果两端点又被滴过的直接搜下一个点；若两端点都未搜过则枚举其中一个，然后回溯枚举另一个。
其中sum>10可以剪枝，最后看ans与10的关系，
复杂度(2^10*m)

以下为AC代码

#define Maxx 2005
#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
}a[Maxx];

int t,n,m,ans;
int vis[Maxx];

void dfs(int u,int sum){
    if(sum>10)return;
    if(u==m){
        ans=min(ans,sum);
        return;
    }
    int xx=a[u].x,yy=a[u].y;
    if(vis[xx]||vis[yy])dfs(u+1,sum);
    else{
        vis[xx]=1;
        dfs(u+1,sum+1);
        vis[xx]=0;
        vis[yy]=1;
        dfs(u+1,sum+1);
        vis[yy]=0;
    }
    return;
}

int main(){
    cin>>t;
    while(t--){
        memset(vis,0,sizeof(vis));
        ans=0x3f3f3f3f;
        cin>>n>>m;
        for(int i=0;i<m;i++){
            cin>>a[i].x>>a[i].y;
        }
        dfs(0,0);
            if(ans<=10)cout<<ans<<endl;
            else cout<<"GG"<<endl;
    }
    return 0;
}