关于DFS心得：
1、利用结构体，记录mark和题目要求的基本属性。
2、用到递归，使用递归时注意要设置出口，即符合要求时return，注意对递归的理解，对于不同情况可能要传递不同的参数，但出口都是一样的。
3、在DFS时可以剪枝，即对明显不符合条件的情况（基本判断，比如正方形的四边一样长，三角形的两边大于第三边）直接排除，不参与递归，在剪枝的时候注意正确的剪枝。所以在DFS超时时可以考虑剪枝。
4、在递归发现不符合条件需要返回上一层的时候，要将不符合条件的元素flag消除（DFS、BFS的区别之一）。
例题：
Problem Description
Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?
Input
The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.
Output
For each case, output a line containing “yes” if is is possible to form a square; otherwise output “no”.
Sample Input
3
4 1 1 1 1
5 11 20 30 40 50
8 1 7 2 6 4 4 3 5
.
Sample Output
yes
no
yes
大神滴代码。。。。。。。。。。。。
//剪支62MSAC
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,cnt,sum;
struct node
{
int lenth;
int mark;
}stick[25];
int cmp(node a,node b)
{
return a.lenth>b.lenth;
}
int dfs(int len,int count,int l,int pos)
{
if(count==4)return 1;
for(int i=pos;i<n;i++)
{
if(stick[i].mark)continue;
if(len==(stick[i].lenth+l))
{
stick[i].mark=1;
if(dfs(len,count+1,0,0))
return 1;
stick[i].mark=0;
return 0;
}
else if(len>(stick[i].lenth+l))
{
stick[i].mark=1;
l+=stick[i].lenth;
if(dfs(len,count,l,i+1))
return 1;
l-=stick[i].lenth;
stick[i].mark=0;
if(l==0) return 0;
while(stick[i].lenth==stick[i+1].lenth)i++;
}
}
return 0;
}
int main()
{
int T;
cin>>T;
while(T--)
{
scanf("%d",&n);
cnt=sum=0;
for(int i=0;i<n;i++)
{
scanf("%d",&stick[i].lenth);
sum+=stick[i].lenth;
stick[i].mark=0;
}
sort(stick,stick+n,cmp);
if(sum%4||n<4)
{
cout<<"no"<<endl;
continue;
}
cnt=sum/4;
if(dfs(cnt,0,0,0))
{
cout<<"yes"<<endl;
}
else
{
cout<<"no"<<endl;
}
}
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
int n,s,k,a[22],visit[22]={0};? //a数组用来记录那一组数据，visit数组用来记录当前组的数据是否可用
void DFS(int sum,int x,int d)? //sum是当前计算的和，等于正方形边长的话就配好了一条边了，x是记录当前配好了多少条边，d是上一次匹配到了哪里，是剪枝的关键
{
if(k||x==3)? //当配上了三边的时候就说明能构成正方形了，如果已经能配成正方形就直接返回了
{
k=1;return;? //k=1标记已经能够成正方形了
}
int i;
for(i=d;i<n;i++)? //从上次断点开始匹配
{
if(k)return;? //已经构成正方形就直接返回
if(!visit[i])? //询问这第i组数据是否可用
if(sum+a[i]==s)? //如果正好配成边
{
visit[i]=1;
DFS(0,x+1,0);? //初始化s和d并已经配成的边+1
visit[i]=0;
}
else if(sum+a[i]<s)? //如果比边小
{
visit[i]=1;
DFS(sum+a[i],x,i+1);? //传送断点和此时的值
visit[i]=0;
}
}
}
bool cmp(int a,int b)
{
return a<b;
}
int main(void)
{
int m,i;
cin>>m;
while(m--&&cin>>n)
{
for(i=s=0;i<n;i++)
cin>>a[i],s+=a[i];? //统计正方形周长
sort(a,a+n,cmp);? //从小到大排序
if(s%4==0)? //判断周长是否是正方形的形式
{
s/=4;? //s变成记录正方形的边长
k=0;? //初始化k
DFS(0,0,0);? //和为0，已配成的边数量为0，断点是起点
if(k)cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
else cout<<"no"<<endl;
}
return 0;
}