搜索+思维

前言：搜索的题目，往往不会明确的告诉你搜索的方式（给图），需要自己把问题抽象出来，否则就完全没有思路。

一、危险系数

大意是:地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
我们来定义一个危险系数DF(x,y)：
对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。
本题的任务是：已知网络结构，求两站点之间的危险系数。

思路:
**1、**首先要明确关键点是什么。从一个站点传到另一个站点可能会有多种路径，在每种路径中可能会存在一个中转站总是出现，也就是缺少它，任何一条路径都无法进行，这就是关键点。
**2、**基于关键点，我们可以搜索起始站到终点站的所有路径并记录中途站，每搜索到一条新路径就把记下每个站点出现的次数
**3、**把路径数目和站点出现次数相比较，若相等，则它是缺一不可的关键点。

#include <bits/stdc++.h>
using namespace std;
int vis[1001][1001],d[1001];//标记站台间是否连通 
int m,n,l,r;//站台数，通道数，起始点，终止点
int ans;//最终求得的路径总数 
int num[1001];//记录每个站点出现多少次 
int c[10000];//记录路径
void dfs(int k,int p)//目前所在站台,目前经过站台数 
{
	if(k==r)
	{
		for(int i=0;i<p-1;i++)//记录中转站，但因为p-1为最后一个为终点，不用记录
			num[c[i]]++;
		ans++;//路径加1
		return;
	}
	for(int i=1;i<=m;i++)//遍历每个站台
	{
		if(vis[k][i]&&d[i]==0)//只要有通道就能走，同时标记避免反复走
		{
			d[i]=1;
			c[p]=i;//记录中转站
			dfs(i,p+1);
			d[i]=0;
		}
	}
}
int main()
{
	cin>>m>>n;
	for(int i=0;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		vis[a][b]=1;
		vis[b][a]=1;
	}
	cin>>l>>r;
	d[l]=1;
	dfs(l,0);
	int zz=0;//最终答案 
	for(int i=1;i<=m;i++)
	{
		if(num[i]==ans)
			zz++;
	}
	cout<<zz;
}

二、围正方形

**题目意思:**有很多长度不一的棍子，全部用上，能否拼成正方形。
思路:
1、可以抽象为给你一堆数字，能否分成四份和相等的序列。但这样考虑并不准确，太盲目了。这道题目要求棍子全部用上，如果能拼成正方形则每条边的长度必然为总长度/4，这样拼的时候就有了目标。
2、如果棍子和不为4的倍数，一定不符合
3、只要拼出三根棍子符合题意，则一定符合题意
4、记录下每次搜索到的棍子编号pos，下次从pos+1搜起，因为前面的都判断过了。如果又从头搜起，会超时。
5、搜索前读入棍子的长度时，用sort把长的排在前面

#include <bits/stdc++.h>
using namespace std;
int a[25],vis[25];//储存棍子长度,标记是否用过 
int n,goal;
bool cmp(int a,int b)
{
	return a>b;
}
bool dfs(int k,int m,int pos)//pos为上次匹配到第几跟
{
	if(k==4)
		return true;
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==0&&a[i]<=m)
		{
			vis[i]=1;
			if(m==a[i])
			{
				if(dfs(k+1,goal,1))
					return true;
			}
			else
			{
				if(dfs(k,m-a[i],i+1))
					return true;
			}
			vis[i]=0;
		}
	}
	return false; 
} 
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		int sumn=0;
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			sumn+=a[i];
		}
		if(sumn%4!=0)
			cout<<"no"<<endl;
		else
		{
			sort(a+1,a+n+1,cmp);
			goal=sumn/4;
			if(dfs(1,goal,1))
				cout<<"yes"<<endl;
			else
				cout<<"no"<<endl;
		}	
	}
}