hdu 5305 Friends dfs

这道题目是多校中的一道题，一直在我的书签待看中，不想看书啊不想看书，这几天都没有好好看书了，没正正经经想过题目，正好这次把它看看，先看的题解。。。我发现我对搜索还是有点兴趣的，今天晚上做做搜索。。。我之前就觉得dfs总是回加上回溯的，我还感觉dfs基本上都是两种情况，1.对点深搜，2.对边深搜

思路：

还是看的别人的思路，厚着脸皮写一下吧，这道题目最多有8个点，(8*7)/2=28条边，我们可以先判断一下是否每个边的度数都是偶数，因为只要有一个是奇数的话就没有方案。所以数据最大是(8*6)/2=24条边，暴力的话还是会T，因为每条边都会有两种情况。我们再思考一下，当一个点的n-1条边都确定之后，最后一条边只有一种情况，所以可以少判断了n-1条边，即判断17条边，可以暴力了。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<algorithm>
#define MAX 0x7fffffff

using namespace std;
int cnt,n,m;
int d1[10],d2[10];//d1，d2数组分别表示online friends的数目 offline friends的数目 
int sum[10];
struct node
{
	int i,j;
}edge[30];//这个数组用来表示边，i，j分别是边的端点 
void dfs(int num)
{
	if(num == m+1)
	{
		int flag = 0;
		for(int i=1; i<=n; i++)
		{
			if(d1[i] != d2[i])
			{
				flag = 1;
				break;
			}
		}
		if(flag == 0)
			cnt ++;
		return;
	}
	int x = edge[num].i;
	int y = edge[num].j;
	if(d1[x] < sum[x]/2 && d1[y] < sum[y]/2)//如果还没有到达一半就加进去 
	{
		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]--;
	}
	return;
}
int main()
{
	int T,i,j,a,b;
	cin >> T;
	while(T -- )
	{
		cin >> n >> m;
		cnt = 0;
		memset(sum,0,sizeof(sum));
		memset(d1,0,sizeof(d1));
		memset(d2,0,sizeof(d2));
		memset(edge,0,sizeof(edge));
			for(i=1; i<=m; i++)
			{
				cin >> a >> b;
				edge[i].i = a;
				edge[i].j = b;
				sum[a]++;//点的边数 
				sum[b]++;
			}
			int flag = 0;
			for(i=1; i<=n; i++)
			{
				if(sum[i]%2 != 0)
				{
					flag = 1;
					break;
				}
			}
			if(flag)
				cout << 0 <<endl;
			else
			{
				dfs(1);
				cout << cnt << endl;
			}
	} 
	return 0;
}

hdu 5305 Friends dfs

原文：http://blog.csdn.net/sinat_22659021/article/details/48004981